Cod sursă (job #307367)

#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define err 1e-12

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int NMAX = 100000 + 15;

struct data{
  long long x;
  long long y;

  bool operator<(data other)const{
    if(err < abs(y - other.y))
      return (y < other.y);
    else
      return (x < other.x);
  }
};

int n, h, last, q, st[1 + NMAX], ok[1 + NMAX];
data v[1 + NMAX];

int check(long long a, long long b){
  if(a + err < b)
    return 1;
  else if(b + err < a)
    return -1;
  return 0;
}

bool cmp(data a, data b){
  int answer = check(a.x, b.x);
  if(answer != 0){
    return (answer == 1);
  }else{
    return(check(a.y, b.y) == 1);
  }
}

int sgn(data a, data b, data c){
  long long x1, y1, z1;
  x1 = a.y - b.y;
  y1 = b.x - a.x;
  z1 = a.x * b.y - b.x * a.y;

  return check(x1 * c.x + y1 * c.y + z1, 0);
}

void solve(){
  int node;
  sort(v + 1, v + n + 1, cmp);

  st[1] = 1;
  st[2] = 2;
  ok[2] = 1;
  node = 3;
  last = 2;
  q = 1;

  while(ok[1] == 0){
    while(ok[node]){
      if(node == n)
        q = -1;
      node += q;
    }

    while(last >= 2 && sgn(v[st[last - 1]], v[st[last]], v[node]) <= 0){
      ok[st[last]] = 0;
      last--;
    }
    st[++last] = node;
    ok[node] = 1;
  }
  h = last - 1;

}

void write(){
  int minn = 1;
  out << h << '\n';
  v[st[1]] = v[st[h + 1]];
  for(int i = 2; i <= h; i++)
    if(v[st[i]] < v[st[minn]])
      minn = i;
  for(int i = minn; i >= 1; i--){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }
  for(int i = h; i > minn; i--){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }
  //for(int i = 2; i <= h + 1; i++){
   // out << st[i] << ' ';// << ' ' << v[st[i]].y << '\n';
  //}
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++){
    in >> v[i].x >> v[i].y;
  }
  in.close();

  solve();
  write();
  out.close();
  return 0;
}