Cod sursă (job #307118)

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct
{
    int x, y;
};
const int NMAX = 100001;
punct a[NMAX], O;
int N, M, s[NMAX];
int prod_vec(punct O, punct A, punct B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int cmp(punct A, punct B)
{
    return prod_vec(O, A, B) > 0;
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int i, j;
    f >> N;
    f >> a[1].x >> a[1].y;
    O = a[1];
    j = 1;
    for (i = 2; i <= N; ++i)
    {
        f >> a[i].x >> a[i].y;
        if (a[i].y < O.y || (a[i].y == O.y && a[i].x < O.x))
            O = a[i], j = i;
    }
    swap(a[1], a[j]);
    sort(a + 2, a + N + 1, cmp);
    M = 2;
    s[1] = 1;
    s[2] = 2;
    for (i = 3; i <= N; ++i)
    {
        while (M >= 2 && prod_vec(a[s[M]], a[i], a[s[M - 1]]) <= 0) M--;
        s[++M] = i;
    }
    if (prod_vec(a[s[M]], O, a[s[M - 1]]) == 0) --M;
    s[M + 1] = s[1], s[M + 2] = s[2];
    for(int i = 1; i <= M; i++)
        if(prod_vec(a[s[i]], a[s[i + 1]], a[s[i + 2]]) == 0) M--, s[i + 1] = 0;;
    g << M << '\n';
    for (i = 1; i <= M; ++i)
        if(s[i] != 0) g << a[s[i]].x << ' ' << a[s[i]].y << '\n';
    return 0;
}