Cod sursă (job #77370)

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

struct puncte{int x,y;};
puncte v[100001],mini,maxi,st[100001];
int n,h;

bool fct(puncte A, puncte B){
    return atan2((double)A.y,(double)A.x)<atan2((double)B.y,(double)B.x);
}

int arie(puncte p1, puncte p2, puncte p3){
    double ar;
    ar=p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p2.y*p3.x -p3.y*p1.x -p1.y*p2.x;
    if(ar<0)
        return -1;
    if(ar==0)
        return 0;
    return 1;
}


int main(){
    int i;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&v[i].x,&v[i].y);
        if(v[i].y<mini.y||i==1)
            mini=v[i];
        if(v[i].y>maxi.y||i==1)
            maxi=v[i];
    }
    for(i=1;i<=n;i++){
        v[i].x-=mini.x;
        v[i].y-=mini.y;
    }

    sort(v+1,v+n+1,fct);
    maxi.x-=mini.x;
    maxi.y-=mini.y;
    h=1;
    puncte origine;
    origine.x=0;
    origine.y=0;
    st[1]=origine;
    for(i=1;i<=n;i++){
        if(v[i].y!=0||v[i].x!=0)
        if(v[i].y!=maxi.y||v[i].x!=maxi.x)
        if(arie(origine,maxi,v[i])<0){
            h++;
            st[h]=v[i];
            while(h>2&&arie(st[h-2],st[h-1],st[h])<=0){
                h--;
                st[h]=v[i];
            }
            v[i].x=0;
            v[i].y=0;
        }
    }
    h++;
    st[h]=maxi;
     while(h>2&&arie(st[h-2],st[h-1],st[h])<=0){
                h--;
                st[h]=maxi;
            }

     for(i=1;i<=n;i++){
        if(v[i].y!=0||v[i].x!=0)
        if(v[i].y!=maxi.y||v[i].x!=maxi.x)
        if(arie(origine,maxi,v[i])>0){
            h++;
            st[h]=v[i];
            while(h>2&&arie(st[h-2],st[h-1],st[h])<=0){
                h--;
                st[h]=v[i];
            }
            v[i].x=0;
            v[i].y=0;
        }
     }
    h++;
    st[h]=origine;
    while(h>2&&arie(st[h-2],st[h-1],st[h])<=0){
                h--;
                st[h]=origine;
            }
    printf("%d\n",h-1);
    for(i=1;i<h;i++){
        printf("%d %d\n",st[i].x+mini.x, st[i].y+mini.y);
    }
return 0;
}