Cod sursă (job #77573)

#include <fstream>
#include <algorithm>
#include <utility>

using namespace std;

#define x first
#define y second

typedef pair<int, int> point;

const int MAX_N = 100000;

int n;
point v[MAX_N];

const int starting_point()
{
    int low = 0;
    for(int i = 1 ; i < n ; ++i)
    {
        if(v[i].y < v[low].y || v[i].y == v[low].y && v[i].x < v[low].x)
            low = i;
    }
    return low;
}

const int ccw(const point &a, const point &b, const point &c)
{
    const int x1 = b.x - a.x,
              y1 = b.y - a.y,
              x2 = c.x - b.x,
              y2 = c.y - b.y;

    return x1 * y2 - x2 * y1;
}

const int ccw(const int &a, const int &b, const int &c)
{
    return ccw(v[a], v[b], v[c]);
}

const int dist(const point &a, const point &b)
{
    const int x = b.x - a.x,
              y = b.y - a.y;

    return x*x + y*y;
}

bool comp(const point &a, const point &b)
{
    const int cross = ccw(v[0], a, b);
    if(cross > 0)
        return 1;
    else if(cross == 0 && dist(a, v[0]) < dist(b, v[0]))
        return 1;
    else
        return 0;
}

void prepare_points()
{
    const int low = starting_point();
    swap(v[low], v[0]);
    sort(v + 1, v + n, comp);
}

int st[MAX_N];
int lv;

void convex_hull()
{
    prepare_points();
    st[0] = 0,
    st[1] = 1;
    lv = 1;

    for(int i = 2 ; i < n ; ++i) {
        while(lv > 0 && ccw(st[lv - 1], st[lv], i) <= 0)
            --lv;
        ++lv;
        st[lv] = i;
    }
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    in >> n;

    for(int i = 0 ; i < n ; ++i)
        in >> v[i].x >> v[i].y;

    convex_hull();

    out << lv + 1 << "\n";

    for(int i = 0 ; i <= lv ; ++i)
        out << v[st[i]].x << " " << v[st[i]].y << "\n";

    return 0;
}