Pagini recente » Cod sursa (job #2538500) | Cod sursa (job #829458) | Cod sursa (job #449159) | Cod sursa (job #2244965) | Cod sursa (job #303121)
Cod sursa(job #303121)
#include <stdio.h>
#include <algorithm>
#define NM 120001
using namespace std;
struct pct{float x,y;} a[NM],minim,st[NM];
int vf;
int n;
int cmp(pct a,pct b)
{if (b.x==minim.x&&b.y==minim.y) return 1;
if (b.x==minim.x) return 1;
if ((a.y-minim.y)*(b.x-minim.x)<(a.x-minim.x)*(b.y-minim.y)) return 1;
return 0;
}
float det(pct a,pct b,pct c)
{return (a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-c.y*a.x);
}
int main()
{freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
{scanf("%f %f",&a[i].x,&a[i].y);
if (minim.x>a[i].x||(minim.x==a[i].x&&minim.y>a[i].y)||i==1)
{minim=a[i];
}
}
sort(a+1,a+n+1,cmp);
st[++vf]=minim;
for (i=1;i<n;i++)
{while (vf>1&&det(st[vf-1],st[vf],a[i])<=0)
{vf--;
}
st[++vf]=a[i];
}
printf("%d\n",vf);
for (i=1;i<=vf;i++)
{printf("%f %f\n",st[i].x,st[i].y);
}
return 0;
}