Cod sursa(job #716670)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 19 martie 2012 09:15:27
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#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;
}