Cod sursă (job #306583)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

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

int const nmax = 100000;
double const zero = 0.0000001;

struct Point {
    int x;
    int y;

    bool operator<(Point other) const {
      if (y != other.y)
        return (y < other.y);
      else
        return (x < other.x);
    }
};

int det3(Point a, Point b, Point c) {
  long long answer = 1LL * a.x * (b.y - c.y) + 1LL * b.x * (c.y - a.y) + 1LL * c.x * (a.y - b.y);
  if (answer == 0)
    return 0;
  else if (0 < answer)
    return 1;
  else
    return -1;
}

int n, nst, np;
Point p[1 + nmax];
Point st[1 + nmax];

bool compare(Point a, Point b) {
  return (det3(p[1], a, b) > 0);
}

void convexhull() {
  nst = 2;
  st[1] = p[1];
  st[2] = p[2];
  for (int i = 3; i <= np; i++) {
    while (2 < nst && (det3(st[nst - 1], st[nst], p[i]) < 0))
      nst--;
    if (det3(st[nst - 1], st[nst], p[i]) == 0) {
      st[nst] = p[i];
    } else {
      nst++;
      st[nst] = p[i];
    }
  }
}

bool onseg(Point a, Point b, Point c) {
  if (min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x))
    if (min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y))
      return 1;
  return 0;
}

int main() {
  in >> n;
  int first = 1;
  for (int i = 1; i <= n; i++) {
    in >> p[i].x >> p[i].y;
    if (p[i] < p[first])
      first = i;
  }
  swap(p[1], p[first]);
  sort(p + 2, p + n + 1, compare);

  //eliminate collinear points
  np = 2;
  for (int i = 3; i <= n; i++) {
    if (det3(p[1], p[np], p[i]) == 0) {
      if (onseg(p[1], p[i], p[np]))
        p[np] = p[i];
    } else {
      np++;
      p[np] = p[i];
    }
  }
//  cout << np << endl;

  convexhull();

  out << nst << endl;
  for (int i = 1; i <= nst; i++)
    out << st[i].x << " " << st[i].y << endl;
  return 0;
}