Pagini recente » Cod sursa (job #711383) | Cod sursa (job #1607130) | Cod sursa (job #2830795) | Cod sursa (job #339143) | Cod sursa (job #995420)
Cod sursa(job #995420)
#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX = 120005;
int N,i,Min,Cnt,St[NMAX];
struct Point {double x,y;} P[NMAX];
double CrossProduct(Point A,Point B,Point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
bool cmp(const Point &A,const Point &B)
{
return CrossProduct(P[1],A,B)<0;
}
void Read()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N); Min=1;
for(i=1;i<=N;i++)
{
scanf("%lf",&P[i].x);
scanf("%lf",&P[i].y);
//if(P[i].x==P[Min].x && P[i].y<P[Min].y) Min=i;
//else if(P[i].x<P[Min].x) Min=i;
}
}
void Sort()
{
for(i=1;i<=N;i++)
if(P[i].x<P[1].x || (P[i].x==P[1].x && P[i].y<P[1].y))
swap(P[i],P[1]);
//swap(P[Min],P[1]);
sort(P+2,P+N+1,cmp);
}
void ConvexHull()
{
St[1]=1; St[2]=2; Cnt=2;
for(i=3;i<=N;i++)
{
while(Cnt>=2 && CrossProduct(P[St[Cnt-1]],P[St[Cnt]],P[i])>0) Cnt--;
St[++Cnt]=i;
}
}
void Write()
{
printf("%d\n",Cnt);
for(i=Cnt;i;i--) printf("%lf %lf\n",P[St[i]].x,P[St[i]].y);
}
int main()
{
Read();
Sort();
ConvexHull();
Write();
return 0;
}