Pagini recente » Cod sursa (job #2661941) | Cod sursa (job #1383839) | Cod sursa (job #849168) | Cod sursa (job #2217235) | Cod sursa (job #1238415)
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1.e-12
using namespace std;
struct POINT
{
double x,y;
};
POINT MPOT[120005];
int st[120000];
inline bool ccw(const POINT &P1, const POINT &P2,const POINT &P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x)>0;
}
inline bool myComp (const POINT &P1, const POINT &P2)
{
return ccw(MPOT[0],P1,P2);
}
int main()
{ freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,top;
scanf("%d%lf%lf",&n,&MPOT[0].x,&MPOT[0].y);
for(i=1; i<n; ++i)
{
scanf("%lf%lf",&MPOT[i].x,&MPOT[i].y);
if((fabs(MPOT[i].y-MPOT[0].y)<eps&&MPOT[i].x-MPOT[0].x<=-eps)||MPOT[i].y-MPOT[0].y<=-eps)
swap(MPOT[0],MPOT[i]);
}
sort(MPOT+1,MPOT+n,myComp);
MPOT[n]=MPOT[0];
st[0]=0;
st[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(MPOT[st[top-1]],MPOT[st[top]],MPOT[i]))
{
st[++top]=i++;
}
else
--top;
}
printf("%d\n",top);
for(i=0;i<top;++i)
printf("%lf %lf\n",MPOT[st[i]].x,MPOT[st[i]].y);
return 0;
}