Cod sursă (job #530577)

#include <bits/stdc++.h>
#define MAX_NR 2147483647

using namespace std;

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

struct punct
{
    long long x,y;
}v[120100],s[120100];

int compare(punct A,punct B)
{
    /// panta1 = (A.x-v[1].x)/(A.y-v[1].y)
    /// panta2 = (B.x-v[1].x)/(B.y-v[1].y)
    /// cand compar fac produs pe diagonala pentru precizie mai mare

    if((A.x-v[1].x)*(B.y-v[1].y)==(A.y-v[1].y)*(B.x-v[1].x)) /// caz daca sunt coliniare
    {
        if(A.x==B.x)return(A.y>B.y);
        return (A.x<B.x);
    }

    return((A.x-v[1].x)*(B.y-v[1].y)>(A.y-v[1].y)*(B.x-v[1].x));
}

int viraj_dreapta(punct A,punct B,punct C)
{
    /// folosim formula cu determinant

    /// (A.x A.y 1)
    /// (B.x B.y 1)
    /// (C.x C.y 1)

    /// acest determinant da semn -1 daca punctul C se afla in dreapta vectorului AB, respectiv semn +1 daca e in stanga
    /// IMPORTANT! este dreapta vectorului, adica este important si sensul

    long long val = (A.x*B.y + B.x*C.y + A.y*C.x - B.y*C.x - C.y*A.x - B.x*A.y);
    if(val<0)return 1;
    else if(val==0)return 0;
    else return -1;
}

long long n,i,poz,T,minix=MAX_NR,miniy=MAX_NR;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i].x>>v[i].y;

        /// cautam un punct care sigur e pe infasuratoare -> cel mai din stanga iar in caz de egalitate, cel mai de jos
        if(v[i].x<minix)
        {
            minix=v[i].x;
            miniy=v[i].y;
            poz=i;
        }
        else if(v[i].x==minix)
        {
            if(v[i].y<miniy)
            {
                miniy=v[i].y;
                poz=i;
            }
        }
    }

    /// il punem pe pozitia 1 pe acel punct aflat anterior
    swap(v[1],v[poz]);

    /// sortam dupa panta pe care o formeaza punctul ales cu puntele celelalte
    sort(v+2,v+n+1,compare);

    /// pun primele 2 puncte in stiva
    T=2;
    s[1]=v[1];
    s[2]=v[2];

    /// parcurg punctele in ordine
    for(i=3;i<=n;i++)
    {
        /// daca virez la stanga, atunci pun punctul
        /// daca virez la dreapta, atunci scot din stiva pana cand obtin viraj la stanga
        /// daca de asemenea obtin puncte coliniare, adica determinantul din "viraj_dreapta" == 0, scot din stiva

        /// virez la st/dr daca punctul "i" se afla pe partea negativa, respectiv pozitia a dreptei determinata de primele 2 puncte din varful stivei (contand sensul dreptei)
        /// la "viraj_dreapta" apelez neaparat in ordinea asta pentru ca ma intereseaza sensul dreptei
        while(T>2 && viraj_dreapta(s[T-1],s[T],v[i])>=0)T--;
        while(T>1 && viraj_dreapta(s[T-1],s[T],v[i])==0)T--;
        T++;s[T]=v[i];
    }

    /// programul afiseaza deja in ordine trigonometrica, dar pentru ca asa vrea problema, trebuie sa incepe intai cu punctul ce are y minim, iar in caz de egalitate x minim

    g<<T<<'\n';
    minix=MAX_NR;miniy=MAX_NR;
    for(i=1;i<=T;i++)
    {
        if(s[i].y<miniy)
        {
            miniy=s[i].y;
            minix=s[i].x;
            poz=i;
        }
        else if(s[i].y==miniy)
        {
            if(s[i].x<minix)
            {
                minix=s[i].x;
                poz=i;
            }
        }
    }
    for(i=poz;i<=T;i++)
        g<<s[i].x<<" "<<s[i].y<<'\n';

    for(i=1;i<poz;i++)
        g<<s[i].x<<" "<<s[i].y<<'\n';
    return 0;
}