Pagini recente » Cod sursa (job #397866) | Cod sursa (job #180598) | Cod sursa (job #916871) | Cod sursa (job #87464) | Cod sursa (job #716670)
Cod sursa(job #716670)
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
double x[120000],y[120000];
long double v[1200];
int pi,v1[120000],N,v2[120000];
int cmp(int i,int j)
{
return (double)(x[i] - x[pi]) * (y[j] - y[pi]) < (double)(x[j] - x[pi]) * (y[i] - y[pi]);
}
long double semn(int i1,int i2,int i3)
{
return (long double)x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&N);
x[0]=1000000000;
y[0]=1000000000;
int punct_initial = 0;
for(int i=1;i<=N;++i)
{
scanf("%lf %lf",&x[i],&y[i]);
if (x[i] < x[punct_initial] || (x[i] == x[punct_initial] && y[i] < y[punct_initial]))
punct_initial = i;
}
pi = punct_initial;
for(int i = 1;i <= N; ++i)
{
if (i == punct_initial) continue;
v1[++v1[0]] = i;
}
sort(v1 + 1,v1 + v1[0] + 1,cmp);
v2[v2[0] = 1] = punct_initial;
for(int i = 1;i <= v1[0]; ++i)
{
if (v1[i] == punct_initial) continue;
while(v2[0] >= 2 && semn(v2[v2[0] - 1],v2[v2[0]],v1[i]) > 0)
--v2[0];
v2[++v2[0]] = v1[i];
}
v2[++v2[0]] = punct_initial;
printf("%d\n",v2[0] - 1);
reverse(v2 + 1, v2 + v2[0] + 1);
for(int i = 1;i < v2[0]; ++i)
printf("%lf %lf\n",x[v2[i]],y[v2[i]]);
return 0;
}