Pagini recente » Cod sursa (job #1566476) | Cod sursa (job #2069848) | Cod sursa (job #1288189) | Cod sursa (job #2855049) | Cod sursa (job #1603685)
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
const double eps=1.e-12;
struct point {double x,y;};
point P[120005],LL;
int n;
double dist(point P1,point P2)
{
return (P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.y);
}
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 ccp;
ccp=cp(P1,P2,P3);
if(fabs(ccp<eps))
return 0;
if(ccp>=eps)
return 1;
return -1;
}
bool cmp(point P1, point P2)
{
double d1,d2;
int cccw;
cccw=ccw(LL,P1,P2);
d1=dist(LL,P1);
d2=dist(LL,P2);
if(cccw==0)
{
if(d1<d2)
return 1;
else return 0;
}
else if(cccw==1)
return 1;
else return 0;
}
using namespace std;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
double a,b;
int i;
scanf("%d",&n);
scanf("%lf%lf",&a,&b);
P[1].x=a;
P[1].y=b;
for(i=2;i<=n;i++)
{
scanf("%lf%lf",&a,&b);
P[i].x=a;
P[i].y=b;
if(P[i].y-P[1].y<=-eps)
swap(P[i],P[1]);
else if(fabs(P[i].y-P[1].y)<eps && (P[i].x-P[1].x)<=-eps)
swap(P[i],P[1]);
}
LL=P[1];
sort(P+2,P+n+1,cmp);
P[n+1]=P[1];
int top=1,st[120005];
st[top]=1;
top++;
st[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--;
}
top--;
printf("%d\n",top);
for(i=1;i<=top;i++)
printf("%lf %lf\n",P[st[i]].x,P[st[i]].y);
return 0;
}