Cod sursă (job #809601)

#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
const int NMAX=100001;

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

struct punct
{
    int x,y;
};

int n,nrp;
punct p[NMAX], st[NMAX];

inline long long patrat(long long x)
{
    return x*x;
}

long long distp(const punct &a, const punct &b)
{
    return patrat(a.x-b.x)+patrat(a.y-b.y);
}

long long det(const punct &a,const punct &b,const punct &c)
{
    return 1LL*(a.x-b.x)*(b.y-c.y)-1LL*(a.y-b.y)*(b.x-c.x);
}

bool compy(const punct &a, const punct &b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

bool compd(const punct &a, const punct &b)
{
    long long dd = det(p[1], a, b);
    if(dd == 0)
        return distp(a, p[1]) < distp(p[1], b);
    return dd > 0;
}

void citire()
{
    fin>>n;
    int pmin=1;
    for(int i=1; i<=n; i++)
    {
        fin>>p[i].x>>p[i].y;
        if(compy(p[i],p[pmin]))
            pmin=i;
    }
    swap(p[1],p[pmin]);
}

void graham()
{
    sort(p+2,p+n+1,compd);
    st[1]=p[1];
    st[2]=p[2];
    nrp=2;
    for(int i=3; i<=n; i++)
    {
        while(nrp>=2&&det(st[nrp-1],st[nrp],p[i])<0)
            nrp--;
        st[++nrp]=p[i];
    }
}

void afisare()
{
    fout<<nrp<<'\n';
    for(int i=1; i<=nrp; i++)
        fout<<st[i].x<<' '<<st[i].y<<'\n';
}

int main()
{
    citire();
    graham();
    afisare();

    fin.close();
    fout.close();
    return 0;
}