Cod sursă (job #817957)

#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct punct{
int x,y;
bool c;//c=0 x,y>0 c=1 x<0
int p,q;//raportul tg=p/q;
}v[100001],s[100001],m;
long long d(punct a,punct b)
{
    return (long long)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(punct a,punct b)
{
    if (a.c==b.c)
    {
        if ((long long)a.p*b.q==(long long)b.p*a.q)
            return d(m,a)<d(m,b);
        return (long long)a.p*b.q<(long long)b.p*a.q;
    }

    return a.c<b.c;
}
long long sens(punct a,punct b,punct c)
{
    long long delta=(long long)(a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-a.x*c.y-b.x*a.y);
    return delta;
}
int main()
{
    int n;
    cin>>n;
    int poz=1;
    m.x=1000000001;
    m.y=1000000001;
    for (int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        if (m.y==v[i].y && m.x>v[i].x)
        {
            poz=i;
            m=v[i];
        }
        if (m.y>v[i].y)
        {
            m=v[i];
            poz=i;
        }
    }
    swap(v[1],v[poz]);
    for (int i=2;i<=n;i++)
    {
        int x1=v[i].x-m.x;
        int y1=v[i].y-m.y;
        if (x1<0)
        {
            v[i].c=1;
        }
        v[i].p=y1;
        v[i].q=x1;
    }
    //cout<<m.x<<" "<<m.y;
    sort (v+2,v+n+1,cmp);
    /*for (int i=1;i<=n;i++)
    {
        cout<<v[i].x<<" "<<v[i].y<<endl;
    }*/
    int t=2;
    s[1]=v[1];
    s[2]=v[2];
    for (int i=3;i<=n;i++)
    {
        while (t>=2 && sens(s[t-1],s[t],v[i])<=0)
        {
            t--;
        }
        t++;
        s[t]=v[i];
    }
    cout<<t<<'\n';
    for (int i=1;i<=t;i++)
    {
        cout<<s[i].x<<" "<<s[i].y<<'\n';
    }
    return 0;
}