Cod sursă (job #77539)

#include <cstdio>
#include <math.h>
#include <iostream>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
};

const double eps = 1.e-14;

Point ll;

int ccw (const Point &A, const Point &B, const Point &C) {
    double cp = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
    if (fabs (cp) < eps)
        return 0;
    if (cp >= eps)
        return 1;
    return -1;
}

double dist (const Point &A, const Point &B) {
    return sqrt (((double)A.x - B.x) * (A.x - B.x) + ((double)A.y - B.y) * (A.y - B.y));
}

class MyComp {
    public :
        bool operator () (const Point &A, const Point &B) {
            int cp;
            double d1, d2;
            cp = ccw (ll, A, B);
            if (cp == 0) {
                d1 = dist (ll, A);
                d2 = dist (ll, B);
                if (d1 - d2 <= -eps)
                    return 1;
                else return 0;
            }
            if (cp == -1)
                return 0;
            return 1;
        }
};

const int N = 100000;

Point P [N + 10];
int H [N + 10];
int n;

int main () {
    int i, poz, u, cp;
    Point aux;

    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);

    scanf ("%d", &n);
    ll.x = ll.y = 1000000000;
    for (i = 1; i <= n; i ++)  {
        scanf ("%d%d", &P [i].x, &P [i].y);
        if (P [i].y < ll.y || (P [i].y == ll.y && P [i].x < ll.x)) {
            ll = P [i];
            poz = i;
        }
    }
    aux = P [1];
    P [1] = P [poz];
    P [poz] = aux;
    sort (P + 2, P + n + 1, MyComp ());
    P [n + 1] = P [1];
    H [1] = 1;
    H [2] = 2;
    i = 3;
    u = 2;
    while (i <= n + 1) {
        if (u >= 2)
            cp = ccw (P [H [u - 1]], P [H [u]], P [i]);
        else {
            H [++ u] = i;
            ++ i;
            continue;
        }
        if (cp > 0) {
            H [++ u] = i;
            ++ i;
        }
        else {
                u --;
        }
    }
    u--;
    printf ("%d\n", u);
    for (i = 1; i <= u; i ++)
        printf ("%d %d\n", P [H [i]].x, P [H [i]].y);
    return 0;
}