Pagini recente » Cod sursa (job #340500) | Cod sursa (job #1770293) | Cod sursa (job #2846832) | Cod sursa (job #1559046) | Cod sursa (job #789262)
Cod sursa(job #789262)
#include<stdio.h>
#include<algorithm>
#define e 1/1000000000
using namespace std;
struct joe
{double x,y;};
bool less(joe a, joe b)
{
if(a.y-b.y<0-e)
return 1;
if(a.y-b.y>-e&&a.y-b.y<e&&a.x-b.x<-e)
return 1;
return 0;
}
joe mi;
double ccw(joe a, joe b, joe c)
{
return (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
bool comp(joe a, joe b)
{
double cp=ccw(mi,a,b);
if(cp>e)
return 1;
if(cp<e)
return 0;
if((a.x-mi.x)*(a.x-mi.x)+(a.y-mi.y)*(a.y-mi.y)>(b.x-mi.x)*(b.x-mi.x)+(b.y-mi.y)*(b.y-mi.y))
return 0;
return 1;
}
joe st[120004];
joe v[120004];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,p=0;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if((mi.x==0&&mi.y==0)||less(v[i], mi))
{
mi.x=v[i].x;
mi.y=v[i].y;
p=i;
}
}
v[p].x=v[1].x;
v[p].y=v[1].y;
v[1].x=mi.x;
v[1].y=mi.y;
sort(v+2,v+n+1,comp);
p=2;
st[1].x=mi.x;
st[1].y=mi.y;
st[2].x=v[2].x;
st[2].y=v[2].y;
for(i=3;i<=n;++i)
{
if(ccw(st[p-1],st[p],v[i])>e)
{
st[++p].x=v[i].x;
st[p].y=v[i].y;
}
else
{
p--;
while(p>1&&ccw(st[p-1],st[p],v[i])<e)
p--;
++p;
st[p].x=v[i].x;
st[p].y=v[i].y;
}
}
printf("%d\n",p);
for(i=1;i<=p;++i)
printf("%lf %lf\n",st[i].x,st[i].y);
return 0;
}