Cod sursă (job #77535)

#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAX_N = 100000;
const int INF = 1000000000;

long long dist(int x1, int y1, int x2, int y2)
{
    return ((long long)(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

struct point2Dint
{
    int x, y;
};

point2Dint points[MAX_N];
point2Dint p0;
point2Dint elements[MAX_N];

int nre;

void push(point2Dint e)
{
    elements[nre].x = e.x;
    elements[nre].y = e.y;
    nre++;
}

void pop()
{
    nre--;
}

point2Dint top()
{
    return elements[nre-1];
}

point2Dint nextToTop()
{
    return elements[nre-2];
}

void change(int a, int b)
{
    point2Dint aux;
    aux.x = points[a].x;
    aux.y = points[a].y;
    points[a].x = points[b].x;
    points[a].y = points[b].y;
    points[b].x = aux.x;
    points[b].y = aux.y;
}

long long ccw(point2Dint p1, point2Dint p2, point2Dint p3)
{
    return ((long long)p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x);
}

bool cmp(point2Dint a, point2Dint b)
{
    int turn = ccw(p0,a,b);
    if(turn == 0)
    {
        return (dist(p0.x,p0.y,a.x,a.y) < dist(p0.x,p0.y,b.x,b.y));
    }
    return (turn > 0);
}

int main()
{
    int n, i;
    int lowestPointIndex;
    p0.y = INF;
    in >> n;
    for(i = 0; i < n; i++)
    {
        in >> points[i].x >> points[i].y;
        if(points[i].y < p0.y)
        {
            p0.y = points[i].y;
            p0.x = points[i].x;
            lowestPointIndex = i;
        } else if(points[i].y == p0.y && points[i].x < p0.x)
        {
            p0.x = points[i].x;
            lowestPointIndex = i;
        }
    }
    change(0,lowestPointIndex);
    nre = 0;
    sort(points+1,points+n,cmp);
    push(points[0]);
    push(points[1]);
    for(i = 2; i < n; i++)
    {
        while(nre >= 2 && ccw(nextToTop(),top(),points[i]) <= 0)
        {
            pop();
        }
        push(points[i]);
    }
    out << nre << "\n";
    for(i = 0; i < nre; i++)
    {
        out << elements[i].x << " " << elements[i].y << "\n";
    }
    in.close();
    out.close();
    return 0;
}