Pagini recente » Cod sursa (job #773252) | Cod sursa (job #80336) | Cod sursa (job #744267) | Monitorul de evaluare | Cod sursa (job #3356261)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double eps=1.e-14;
const int NMAX=120000;
struct POINT
{
double x,y;
};
POINT P[NMAX+5],LL;
int h[NMAX+5];
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 product;
product=cp(P1,P2,P3);
if(fabs(product)<eps)
return 0;
if(product>=eps)
return 1;
return -1;
}
bool cmp(POINT A,POINT B)
{
if(ccw(LL,A,B)==-1)
return 0;
else
return 1;
}
int main()
{
int n,i,r,top;
fin>>n;
fin>>P[1].x>>P[1].y;
for(i=2;i<=n;i++)
{
fin>>P[i].x>>P[i].y;
if(fabs(P[i].y-P[1].y)<eps&&(P[i].x-P[1].x<=-eps))
swap(P[1],P[i]);
else if(P[i].y-P[1].y<=-eps)
swap(P[1],P[i]);
}
LL=P[1];
sort(P+2,P+n+1,cmp);
P[n+1]=LL;
/*for(i=1;i<=n+1;i++)
fout<<P[i].x<<" "<<P[i].y<<"\n";*/
i=3;
h[1]=1;h[2]=2;top=2;
while(i<=n+1)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])==-1)
top--;
else
{
h[++top]=i;
i++;
}
}
fout<<fixed<<showpoint;
fout<<top-1<<"\n";
for(i=1;i<top;i++)
fout<<setprecision(6)<<P[h[i]].x<<" "<<P[h[i]].y<<"\n";
return 0;
}