Cod sursă (job #307114)

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long llong;

struct vec2
{
    int x, y;
    vec2(int xx, int yy) : x(xx), y(yy) {}
    vec2(int a = 0) : x(a), y(a) {}

    inline llong len2() const { return 1LL * x * x + 1LL * y * y; }
    inline llong crossZ(const vec2& a) const { return 1LL * x * a.y - 1LL * y * a.x; }
    inline vec2 operator+(const vec2& a) const { return vec2(x + a.x, y + a.y); }
    inline vec2 operator-(const vec2& a) const { return vec2(x - a.x, y - a.y); }
} v[120001];

inline llong crossZ(const vec2& a, const vec2& b) { return a.crossZ(b); }

bool cmp(const vec2& a, const vec2& b)
{
    vec2 v0a = a - v[0];
    vec2 v0b = b - v[0];
    llong d = crossZ(v0a, v0b);
    if(d == 0)
    {
        if(v0a.len2() < v0b.len2())
            return true;
        return false;
    }
    return d > 0;
}

int n;
int h[120001], lh;

int main()
{
    vec2 vaux;
    int i;
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        if(v[i].y < v[0].y || (v[i].y == v[0].y && v[i].x < v[0].x))
        {
            vaux = v[0];
            v[0] = v[i];
            v[i] = vaux;
        }
    }
    sort(v + 1, v + n, cmp);
    h[0] = 0;
    h[1] = 1;
    lh = 2;
    v[n] = v[0];
    for(i = 2; i <= n; i++)
    {
        while(lh >= 2 && crossZ(v[i] - v[h[lh - 2]], v[h[lh - 1]] - v[h[lh - 2]]) >= 0)
            lh--;
        h[lh++] = i;
    }
    lh--;
    printf("%d\n", lh);
    for(i = 0; i < lh; i++)
    {
        printf("%d %d\n", v[h[i]].x, v[h[i]].y);
    }
    return 0;
}