Cod sursa(job #256641)
#include <stdio.h>
#include <cmath>
#define NMAX 120002
typedef struct punct {double x, y;} Punct;
Punct P[NMAX],S[NMAX];
int n;
double u[NMAX];
void citire()
{ FILE *fin=fopen("infasuratoare.in","r");
fscanf(fin,"%d",&n);
int i;
for (i=0;i<n;i++)
fscanf(fin,"%lf%lf",&P[i].x,&P[i].y);
fclose(fin);
}
void pct_st_jos()
{int i;
for (i=1;i<n;i++)
if (P[i].y<P[0].y || (abs(P[i].y-P[0].y)<0.0000001&& P[i].x<P[0].x))
{
Punct aux=P[i]; P[i]=P[0];P[0]=aux;
}
}
double dif(double a, double b)
{
return fabs(a-b);
}
double dist(Punct a, Punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int pivot(int i, int j)
{ int st,dr,di,dj;
st=i; dr=j; di=1; dj=0;
while (st<dr)
{
if (u[st]>u[dr]) {Punct aux=P[st]; P[st]=P[dr]; P[dr]=aux;
double at=u[st];u[st]=u[dr]; u[dr]=at;
di=di^1; dj=dj^1;
}
else
if (dif(u[st],u[dr])<0.000001)
if (dist(P[0],P[st])>dist(P[0],P[dr]))
{Punct aux=P[st]; P[st]=P[dr]; P[dr]=aux;
di=di^1; dj=dj^1;
}
st+=di; dr-=dj;
}
return st;
}
void qsort(int st, int Dr)
{
if (st<Dr) {
int p=pivot(st,Dr);
qsort(st,p-1);
qsort(p+1,Dr);
}
}
void polar()
{ int i;
for (i=1;i<n;i++)
if (dif(P[i].x,P[0].x)<0.00001&&dif(P[i].y,P[0].y)<0.000001)u[i]=0;
else u[i]=atan2(P[i].y-P[0].y,P[i].x-P[0].x);
qsort(1,n-1);
}
double sens(Punct P1, Punct P2, Punct P3)
{
return ((P2.x-P1.x)*(P3.y-P1.y)-(P3.x-P1.x)*(P2.y-P1.y));
}
int main()
{
citire();
pct_st_jos();
polar();
int l,i;
S[0]=P[0]; S[1]=P[1]; l=1;
for (i=2;i<n;i++)
{
double o=sens(S[l-1],S[l],P[i]);
if (dif(o,0)<0.000001) {S[l]=P[i];}
else
{
while(o<=0&&l>1) {l--;o=sens(S[l-1],S[l],P[i]);}
S[++l]=P[i];
}
}
FILE *fout=fopen("infasuratoare.out","w");
fprintf(fout,"%d\n",l+1);
for (i=0;i<=l;i++)
fprintf(fout,"%lf %lf\n",S[i].x,S[i].y);
fclose(fout);
return 0;
}