Pagini recente » Cod sursa (job #2150105) | Borderou de evaluare (job #2285087) | Cod sursa (job #623493) | Cod sursa (job #623492) | Cod sursa (job #1450400)
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1.e-14;
struct point
{
double x,y;
};
point p[120005],ll;
int st[120005];
double cp(point p1,point p2,point p3)
{
return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(point p1,point p2,point p3)
{
double ans=cp(p1,p2,p3);
if (ans<=-eps)
return -1;
if (ans>=eps)
return 1;
return 0;
}
double dist(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
bool cmp(point a,point b)
{
int ans=ccw(ll,a,b);
if (ans==0)
return dist(ll,a)<dist(ll,b);
if (ans==1)
return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,n,top;
scanf("%d",&n);
scanf("%lf%lf",&p[1].x,&p[1].y);
for(i=2;i<=n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if (p[i].y-p[1].y<=-eps)
swap(p[1],p[i]);
else
if (fabs(p[i].y-p[1].y)<eps)
if (p[i].x-p[1].x<=-eps)
swap(p[1],p[i]);
}
ll=p[1];
sort(p+2,p+n+1,cmp);
p[n+1]=ll;
st[1]=1;
st[2]=2;
top=2;
i=3;
while(i<=n+1)
{
if (ccw(p[st[top-1]],p[st[top]],p[i])>0)
st[++top]=i,i++;
else
top--;
}
printf("%d\n",top-1);
for(i=1;i<top;i++)
printf("%lf %lf\n",p[st[i]].x,p[st[i]].y);
return 0;
}