Pagini recente » Cod sursa (job #2712485) | Cod sursa (job #872581) | Cod sursa (job #392159) | Cod sursa (job #1532195) | Cod sursa (job #2756386)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int h[10000] , top ;
const double eps=1.e-14;
struct punct
{
double x ,y ;
}P[120005] , LL ;
double cp(punct P1, punct P2 , punct P3)
{
return (P2.x-P1.x)*(P3.y-P2.y) - (P2.y-P1.y)*(P3.x-P2.x) ;
}
int ccw(punct P1,punct P2,punct P3)
{
double cpp = cp(P1,P2,P3) ;
if(fabs(cpp)<eps)
return 0 ;
if(cpp>eps)
return 1;
return -1 ;
}
bool cmp(punct P1,punct P2)
{
int ccww;
ccww=ccw(LL,P1,P2) ;
return ccww==1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n , i ;
scanf("%d",&n);
scanf("%lf %lf",&P[1].x,&P[1].y);
for(i=2;i<=n;i++)
{
scanf("%lf %lf",&P[i].x,&P[i].y);
if((P[i].y-P[1].y<=-eps)||((fabs(P[i].y-P[1].y)<eps)&&(P[i].x-P[1].x<=-eps)))
swap(P[1],P[i]);
}
LL=P[1];
sort(P+2,P+n+1,cmp);
P[n+1]=LL;
top = 1;
h[top] = 1;
h[++top]=2 ;
i = 3;
while(i<=n+1)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
printf("%d\n",top-1);
for(i=1;i<=top-1;i++)
{
printf("%f %f\n",P[h[i]].x,P[h[i]].y);
}
return 0;
}