Pagini recente » Cod sursa (job #2429244) | Cod sursa (job #2570604) | Cod sursa (job #811520) | Cod sursa (job #311359) | Cod sursa (job #1067655)
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct
{
double x,y;
} a[120005];
int n,k,poz=1;
int st[120005];
double det(punct a, punct b, punct c) {
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int cmp(punct a, punct b) {
punct c;
c.x = c.y = 0;
return det(c,a,b) >=0 ;
}
int main()
{
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if (a[i].y<a[poz].y) poz=i;
else if (a[i].y==a[poz].y && a[i].x<a[poz].x) poz=i;
}
punct aux=a[poz];
a[poz]=a[1], a[1]=aux;
for (i=1;i<=n;++i)
a[i].x-=aux.x, a[i].y-=aux.y;
sort(a+2,a+n+1,cmp);
st[1]=1, st[2]=2, k=2;
for (i=3;i<=n;++i)
{
while (k>=2 && det(a[st[k-1]],a[st[k]],a[i])<0)
--k;
st[++k]=i;
}
printf("%d\n",k);
for (i=1;i<=k;++i)
printf("%lf %lf\n",a[st[i]].x+aux.x,a[st[i]].y+aux.y);
return 0;
}