Cod sursa(job #386687)
#include<fstream.h>
#include<math.h>
struct punct{
double x;
double y;
double d;
double c;
};
punct a[130000];
long s[130000];
long n,k,vf;
void cit()
{ifstream fin("infasuratoare.in");
fin>>n;
long i;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
fin.close();
}
void stjos()
{double minx,miny;
long i;
minx=a[1].x;
miny=a[1].y;
k=1;
for(i=2;i<=n;i++)
if(miny>a[i].y)
{miny=a[i].y;
minx=a[i].x;
k=i;
}
else
if(miny==a[i].y)
if(minx>a[i].x)
{miny=a[i].y;
minx=a[i].x;
k=i;
}
a[0].x=a[k].x;
a[0].y=a[k].y;
for(i=k+1;i<=n;i++)
a[i-1]=a[i];
n--;
}
ofstream fout("infasuratoare.out");
void calc()
{long i;
for(i=1;i<=n;i++)
{a[i].d=sqrt( (a[i].x-a[0].x)*(a[i].x-a[0].x)+ (a[i].y-a[0].y)*(a[i].y-a[0].y) );
a[i].c=(a[i].x-a[0].x)/a[i].d;
}
}
long cmp(long i,long j)
{if(a[i].c>a[j].c)
return 1;
else
if(a[j].c>a[i].c)
return -1;
else
if(a[j].c==a[i].c)
{if(a[i].d>a[j].d)
return 1;
else
return -1;
}
}
long divide(long st,long dr)
{punct x=a[st];
a[n+1]=a[st];
while(st<dr)
{while(st<dr&&cmp(dr,n+1)<0)
dr--;
a[st]=a[dr];
while(st<dr&&cmp(st,n+1)>0)
st++;
a[dr]=a[st];
}
a[st]=x;
return st;
}
void quick(int p,int u)
{long m;
if(p<u)
{m=divide(p,u);
quick(p,m-1);
quick(m+1,u);
}
}
void elimin()
{long i=1,j,sw;
double di;
while(i<n)
{
if(a[i].c==a[i+1].c)
{
for(j=i+1;j<n;j++)
a[j]=a[j+1];
n--;
}
else
i++;
}
}
void stiva()
{long i;
double x1,y1,x2,y2,x3,y3,de;
for(i=0;i<=2;i++)
s[i]=i;
vf=2;
for(i=3;i<=n;i++)
{x1=a[s[vf-1]].x;
y1=a[s[vf-1]].y;
x2=a[s[vf]].x;
y2=a[s[vf]].y;
x3=a[i].x;
y3=a[i].y;
de=x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
while(de<0&&vf>0)
{vf--;
x1=a[s[vf-1]].x;
y1=a[s[vf-1]].y;
x2=a[s[vf]].x;
y2=a[s[vf]].y;
x3=a[i].x;
y3=a[i].y;
de=x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}
vf++;
s[vf]=i;
}
}
void afis()
{ long j,i=0;
a[0].c=2;
fout<<vf+1<<'\n';
for(j=0;j<=vf;j++)
fout<<a[s[j]].x<<" "<<a[s[j]].y<<'\n';
fout.close();
}
int main()
{cit();
stjos();
calc();
quick(1,n);
elimin();
stiva();
afis();
return 0;
}