Cod sursă (job #334295)

#include <fstream>
#include <algorithm>
#define Nmax 1<<17
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {int x,y;} v[Nmax];
int n,s[Nmax],uz[Nmax];
inline int cmp(const punct &a, const punct &b)
{   if(a.y<b.y) return 1; if(a.y>b.y) return 0;
    if(a.x<b.x) return 1; if(a.x>b.x) return 0;
 return 1;
}
int semn(punct a, punct b, punct c)
{   int A=a.y-b.y,B=b.x-a.x,C=1LL*a.x*b.y-1LL*b.x*a.y;
    if(1LL*A*c.x+1LL*B*c.y+C<0) return -1; else return 1;
}
bool coliniare(punct a,punct b,punct c)
{
    return (1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.y*b.x-1LL*b.y*c.x-1LL*c.y*a.x==0);
}
int main()
{   f>>n;
    int i,pas=1,k;
    for(i=1;i<=n;++i) f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    s[1]=1; s[2]=2; uz[2]=1; k=2; i=3;
    while (!uz[1])
	{   while(uz[i])
		{   if(i==n) pas=-1;
			i+=pas;
		}
        while(k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1) uz[s[k--]]=0;
        while(k>=2&&coliniare(v[s[k-1]],v[s[k]],v[i])) --k;
        s[++k]=i; uz[i]=1;
	}
	k--;
	while(k>=3&&coliniare(v[s[k-1]],v[s[k]],v[s[1]])) --k;
	g<<k<<'\n';
    for(i=1;i<=k;i++) g<<v[s[i]].x<<' '<<v[s[i]].y<<'\n';
    g.close(); return 0;
}