Pagini recente » Cod sursa (job #576884) | Cod sursa (job #1799818) | Cod sursa (job #1608767) | Cod sursa (job #1702730) | Cod sursa (job #366130)
Cod sursa(job #366130)
#include <stdio.h>
#include <math.h>
//# define pi 3.1415926535
struct point {double x,y,unghi;};
point aux,ll,pivot,v[120002],st[120002];
//int st[120002];
double pi=3.1415926535;
double dist( point a,point b)
{ double x;
x=sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
return x;
}
int prod(point a,point b,point c)
{
double cp;
cp=(b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
if(cp>0) return 1;
if(cp==0) return 0;
return -1;
}
long partitionare( long st,long dr)
{long m,i,j;
m=(st+dr)/2;
pivot=v[m];
i=st-1;
j=dr+1;
while (1)
{
do {++i;}
while ((v[i].unghi<pivot.unghi)||(v[i].unghi==pivot.unghi&&dist(v[1],v[i])<dist(v[1],pivot)));
do {--j;}
while ((v[j].unghi>pivot.unghi)||(v[j].unghi==pivot.unghi&&dist(v[1],v[j])>dist(v[1],pivot)));
if (i<j)
{aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
return j;
}
}
void quicks( long st,long dr)
{ long p;
if (st<dr)
{p=partitionare(st,dr);
quicks(st,p);
quicks(p+1,dr);
}
}
int main()
{ freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
long n,i,poz,varf;
double t;
scanf ("%ld",&n);
scanf ("%lf %lf",&v[1].x,&v[1].y);
ll=v[1];
poz=1;
for (i=2;i<=n;i++)
{scanf ("%lf %lf",&v[i].x,&v[i].y);
if (ll.y>v[i].y||(ll.y==v[i].y&&ll.x>v[i].x))
{ll=v[i];
poz=i;
}
}
aux=v[poz];
v[poz]=v[1];
v[1]=aux;
for (i=2;i<=n;i++)
{if (v[i].x!=v[1].x)
{t=(v[i].y-v[1].y)/(v[i].x-v[1].x);
if (t>=0) v[i].unghi=atan(t);
else v[i].unghi=atan(t)+pi;
}
else
v[i].unghi=pi/2;
}
quicks (2,n);
st[1]=v[1];
st[2]=v[2];
varf=2;
for (i=3;i<=n;i++)
{if (prod(st[varf-1],st[varf],v[i])>0)
st[++varf]=v[i];
while (prod(st[varf-1],st[varf],v[i])<=0)
varf--;
st[++varf]=v[i];
}
printf ("%ld\n",varf);
for (i=1;i<=varf;i++)
printf ("%lf %lf\n",st[i].x,st[i].y);
return 0;
}