Cod sursă (job #77632)

#include <iostream>
#include <fstream>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;

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

struct point
{
    long long x;
    long long y;
}p[100000];

long long abso(long long x){return x<0?-x:x;}

struct elem
{
    double val;
    int i;
}slope[100000];

bool compare(elem e1, elem e2){return e1.val<e2.val;}

double isLeft(point a, point b, point c)
{
     return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));
}

void write(stack<int> stk)
{
    if(!stk.empty())
    {
        int x=stk.top();
        stk.pop();
        write(stk);
        fout<<p[x].x<<' '<<p[x].y<<'\n';
    }
}

int main()
{

    stack<int> hull; while(!hull.empty()){hull.pop();}

    int n;

    int mini=0, minv, minx;

    fin>>n;

    //if(n<=3){for(int i=1;i<=n;i++)cout<<n<<'\n'; return 0;}

    fin>>p[0].x>>p[0].y;

    minv=p[0].y;
    minx=p[0].x;

    for(int i=1;i<n;i++)
    {
        fin>>p[i].x>>p[i].y;
        if(p[i].y<minv||(p[i].y==minv&&p[i].x<minx))
        {
            minv=p[i].y;
            minx=p[i].x;
            mini=i;
        }
    }

    hull.push(mini);

    for(int i=0;i<n;i++)
    {
        if(i!=mini)
        {
            slope[i].val=atan2(p[i].y-minv,p[i].x-p[mini].x);
        }
        else slope[i].val=10;//big number so it's the last

        slope[i].i=i;
    }

    sort(slope,slope+n,compare);

    //eliminate starting point
    n--;

    long long first=-1, delta=-1, deltai;
    do
    {
        first++;
        long long d = (p[slope[first].i].x==p[mini].x) ? (abso(p[slope[first].i].y-p[mini].y)) : (abso(p[slope[first].i].x-p[mini].x));
        if(d>delta){delta=d; deltai=slope[first].i;}
    }while(slope[first].val==slope[first+1].val);

    hull.push(deltai);

    int i;
    for(i=first+1;slope[i].val!=slope[n-1].val;i++)
    {
        int a,b,o;
        do
        {
            b=hull.top();
            hull.pop();
            a=hull.top();
            o=isLeft(p[a],p[b],p[slope[i].i]);
            if(o==0){

            }
        }while(o<=0);
        hull.push(b);
        hull.push(slope[i].i);

    }

    delta=-1;
    for(first=i;first<n;first++)
    {
        long long d = (p[slope[first].i].x==p[mini].x) ? abso(p[slope[first].i].y-p[mini].y) : abso(p[slope[first].i].x-p[mini].x);
        if(d>delta){delta=d; deltai=slope[first].i;}
    }

    hull.push(deltai);

    fout<<hull.size()<<'\n';
    write(hull);

return 0;
}