Cod sursă (job #307376)

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

using namespace std;

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

const int NMAX = 120000;

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 n, minn = 1;
int st[1 + NMAX], last;
Point v[1 + NMAX];

long long det(Point a, Point b, Point c) {
  long long plus = a.x * b.y + b.x * c.y + a.y * c.x;
  long long minus = c.x * b.y + a.y * b.x + a.x * c.y;
  return (plus - minus);
}

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

long long sgn(Point a, Point b, Point c){
  long long x1, y1, z1;
  x1 = a.y - b.y;
  y1 = b.x - a.x;
  z1 = (1LL * a.x * b.y - 1LL * b.x * a.y);

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

bool cmp(Point b, Point c){
  Point a = v[1];
  int d = sgn(a, b, c);
  if(d != 0)
    return (d < 0);
  else
    return (b < c);
}

int main()
{
  in >> n;
  for(int i = 1; i <= n; i++){
    in >> v[i].x >> v[i].y;
    if(v[i] < v[minn])
      minn = i;
  }
  in.close();
  swap(v[1], v[minn]);
  sort(v + 2, v + n + 1, cmp);

  st[1] = 1;
  st[2] = 2;
  last = 2;

  for(int i = 3; i <= n; i++){
    while(last >= 2 && sgn(v[st[last - 1]], v[st[last]], v[i]) >= 0)
      last--;
    st[++last] = i;
  }

  out << last << '\n';

  minn = 1;
  for(int i = 2; i <= last; i++)
    if(v[st[minn]] < v[st[i]])// compara daca v[st[minn]] este ami mic decar v[st[i]] dupa y si dupa x
      minn = i;

  for(int i = minn; i <= last; i++){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }
  for(int i = 1; i <= minn - 1; i++){
    out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
  }
  out.close();
  return 0;
}