Pagini recente » Cod sursa (job #333580) | Cod sursa (job #1607499) | Cod sursa (job #888694) | Cod sursa (job #2184354) | Cod sursa (job #1238404)
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define eps 1.e-12
using namespace std;
struct POINT
{
double x,y;
};
POINT POINTS[120005];
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(POINTS[0],P1,P2);
}
int st[120000];
int main()
{ freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,top;
scanf("%d%lf%lf",&n,&POINTS[0].x,&POINTS[0].y);
for(i=1; i<n; ++i)
{
scanf("%lf%lf",&POINTS[i].x,&POINTS[i].y);
if((fabs(POINTS[i].y-POINTS[0].y)<eps&&POINTS[i].x-POINTS[0].x<=-eps)||POINTS[i].y-POINTS[0].y<=-eps)
swap(POINTS[0],POINTS[i]);
}
sort(POINTS+1,POINTS+n+1,myComp);
POINTS[n]=POINTS[0];
st[0]=0;
st[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(POINTS[st[top-1]],POINTS[st[top]],POINTS[i]))
{
st[++top]=i;
++i;
}
else
--top;
}
printf("%d\n",top);
for(i=0;i<top;++i)
printf("%lf %lf\n",POINTS[st[i]].x,POINTS[st[i]].y);
return 0;
}