Pagini recente » Cod sursa (job #3244488) | Cod sursa (job #2520500) | Cod sursa (job #273781) | Cod sursa (job #1082739) | Cod sursa (job #326473)
Cod sursa(job #326473)
#include<stdio.h>
#include<math.h>
#define eps 0.000000000001
#define nmax 120010
long n,w;
typedef struct {long double x,y;}point;
point p[nmax],ll,st[nmax];
void read()
{
scanf("%ld",&n);
long i,w;
w=1;
scanf("%Lf%Lf",&p[1].x,&p[1].y);
ll=p[1];
for (i=2;i<=n;i++)
{
scanf("%Lf%Lf",&p[i].x,&p[i].y);
if ((p[i].y-ll.y)<(-1)*eps)
{
ll=p[i];
w=i;
}
else if (fabs(p[i].y-ll.y)<=eps)
{
if ((p[i].x-ll.x)<(-1)*eps)
{
ll=p[i];
w=i;}
}
}
point aux;
aux=p[1];
p[1]=p[w];
p[w]=aux;
}
long cp(point p1,point p2,point p3)
{
long double p;
p=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
if (p<(-1)*eps)
return -1;
if (p>eps)
return 1;
return 0;
}
long double dist(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
long part(long st,long dr)
{
long i,j,s;
point piv,aux;
i=st-1;
j=dr+1;
piv=p[(st+dr)/2];
while (1)
{
do {i++;s=cp(p[1],p[i],piv);}while (s>0 || (s==0 && dist(p[1],piv)>dist(p[1],p[i])));
do {j--;s=cp(p[1],piv,p[j]);}while (s>0 || (s==0 && dist(p[1],p[j])>dist(p[1],piv)));
if (i<j)
{
aux=p[i];
p[i]=p[j];
p[j]=aux;
}
else return j;
}
}
void quicks(long st,long dr)
{
long p;
if (st<dr)
{
p=part(st,dr);
quicks(st,p);
quicks(p+1,dr);
}
}
void convex()
{
long i;
st[1]=p[1];
w=2;
st[w]=p[2];
for (i=3;i<=n;i++)
{
while (w>2 && cp(st[w-1],st[w],p[i])<0)
{
w--;
}
st[++w]=p[i];
}
while (w>2 && cp(st[w-1],st[w],p[1])<0)
{
w--;
}
}
void print()
{
long i;
printf("%ld\n",w);
for (i=1;i<=w;i++)
{
printf("%Lf %Lf\n",st[i].x,st[i].y);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
quicks(2,n);
convex();
print();
return 0;
}