Cod sursa(job #295029)

Utilizator cotofanaCotofana Cristian cotofana Data 2 aprilie 2009 22:09:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <algorithm>
#define dim 120100

using namespace std;

int n, s[dim], ind[dim], in;
double x[dim], y[dim];

long double semn(int n1, int n2, int n3)
{
	return (long double)x[n1]*y[n2]+x[n2]*y[n3]+x[n3]*y[n1]-y[n1]*x[n2]-y[n2]*x[n3]-y[n3]*x[n1];
}

bool cmpf(int i, int j)
{
	return (double)(x[i]-x[in])*(y[j]-y[in])<(double)(x[j]-x[in])*(y[i]-y[in]);
}

void graham()
{
	int i;
	s[1]=in;
	s[0]=1;
	for (i=1; i<=ind[0]; i++)
	{
		while (s[0]>=2 && semn(s[s[0]-1], s[s[0]], ind[i])>0) 
			--s[0];
		s[++s[0]]=ind[i];
	}
	s[++s[0]]=in;
}

int main()
{
	int i;
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d\n", &n);
	x[0]=10e11;
	y[0]=10e11;
	in=0;
	for (i=1; i<=n; i++) 
	{
		scanf("%lf %lf\n", &x[i], &y[i]);
		if (x[i]<x[in] || (x[i]==x[in] && y[i]<y[n])) in=i;
	}
	for (i=1; i<=n; i++)
	{
		if (i==in) continue;
		ind[++ind[0]]=i;
	}
	sort(ind+1, ind+ind[0]+1, cmpf);
	graham();
	printf("%d\n", s[0]-1);
	reverse(s+1, s+s[0]+1);
	for (i=1; i<s[0]; i++) printf("%lf %lf\n", x[s[i]], y[s[i]]);
	return 0;
}