Pagini recente » Clasament preONI 2007, Runda 4, Clasa a 9-a si gimnaziu | Cod sursa (job #192570) | Cod sursa (job #352693) | Cod sursa (job #1773065) | Cod sursa (job #328564)
Cod sursa(job #328564)
#include<stdio.h>
double infinit=1000000001;
struct POINT
{
float x,y;
}; POINT p[120010],pp,aux,s[120010];
long n,i,poz,k;
void read()
{
scanf("%ld",&n);
scanf("%f%f",&p[1].x,&p[1].y);
pp=p[1];poz=1;
for(i=2;i<=n;++i)
{
scanf("%f%f",&p[i].x,&p[i].y);
if(pp.y>p[i].y)
pp=p[i],poz=i;
else
if(pp.y==p[i].y)
if(pp.x>p[i].x)
pp=p[i],poz=i;
}
//--
aux=p[poz]; p[poz]=p[1]; p[1]=aux;
//--
}
double ctg(POINT A, POINT B)
{
if(A.y==B.y)
if(B.x-A.x>0) return infinit;
else return -infinit;
return ((B.x-A.x)/(B.y-A.y));
}
long part(long st, long dr)
{
long i,j,m;
double pivot;
m=(st+dr)/2;
pivot=ctg(pp,p[m]);
i=st-1;j=dr+1;
while(1)
{
do{++i;}while(ctg(pp,p[i])<pivot);
do{--j;}while(ctg(pp,p[j])>pivot);
if(i<j)
{
aux=p[i];
p[i]=p[j];
p[j]=aux;
}
else return j;
}
}
void quicks(long st, long dr)
{
long pe;
if(st<dr)
{
pe=part(st,dr);
quicks(st,pe);
quicks(pe+1,dr);
}
}
void rev()
{
for(i=2;i<=(2+n)/2;++i)
{
aux=p[i];
p[i]=p[n-i+2];
p[n-i+2]=aux;
}
}
int ccw(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;
}
void infasuratoare()
{
s[1]=p[1];
s[2]=p[2];
k=2;
for(i=3;i<=n;++i)
{
if(ccw(s[k-1],s[k],p[i])>=0)
s[++k]=p[i];
else
{
while(ccw(s[k-1],s[k],p[i])<0) k--;
s[++k]=p[i];
}
}
printf("%ld\n",k);
for(i=1;i<=k;++i) printf("%f %f\n",s[i].x,s[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
quicks(2,n);
rev();
infasuratoare();
return 0;
}