Pagini recente » Cod sursa (job #381685) | preoni_0 | Cod sursa (job #1247488) | Cod sursa (job #2185844) | Cod sursa (job #1275253)
//#include <iostream>
#include <algorithm>
#include <cstdio>
#define nmax 120001
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
struct punct{
double x,y;
}v[nmax];
int viz[nmax];
bool comp(punct a, punct b)
{
if(a.x<b.x)
return 1;
if(a.x==b.x&&a.y<b.y)
return 1;
return 0;
}
bool det(punct a, punct b, punct c)
{
return a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-c.x*b.y>0;
}
int main()
{
int semn=1,st[nmax];
long n,i,j,k;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,comp);
st[1]=1; st[2]=2;
k=2;
viz[2]=1;
for(i=3;i;i+=semn)
if(!viz[i])
{
while(k>1&&det(v[st[k-1]],v[st[k]],v[i])==0)
viz[st[k--]]=0;
st[++k]=i;
viz[i]=1;
if(i==n)
semn=-1;
}
fprintf(g,"%d\n",k-1);
for(i=1;i<k;i++)
fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}