Cod sursa(job #729243)

Utilizator paulbotabota paul paulbota Data 29 martie 2012 13:43:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<math.h>
#include<cstdio>
#include<algorithm>
#define maxn 120010
#define inF "infasuratoare.in"
#define outF "infasuratoare.out"

using namespace std;

ifstream in(inF);

double X[maxn],Y[maxn];
int N,origine=1,v[maxn],coada[maxn];

bool cmp(int x,int y)
{
	return (X[x]-X[origine])*(Y[y]-Y[origine])<(X[y]-X[origine])*(Y[x]-Y[origine]);
}

long double unghi(int x, int y, int z)
{
	return (X[x]*Y[y]+X[y]*Y[z]+X[z]*Y[x])-(Y[x]*X[y]+Y[y]*X[z]+Y[z]*X[x]);
}

void read()
{
	in>>N;
	for(int i=1;i<=N;i++)
	{
		in>>X[i]>>Y[i];
		if(X[i]<X[origine] || (X[i]==X[origine] && Y[i]<Y[origine])) origine=i;
	}
}

int main()
{
	int i;
	read();
	for(i=1;i<=N;i++)
	{
		if(i==origine) continue;
		v[++v[0]]=i;
	}
	sort(v+1,v+v[0]+1,cmp);
	coada[coada[0]=1]=origine;
	for(i=1;i<=v[0];i++)
	{
		if(v[i]==origine) continue;
		while(coada[0]>=2 && unghi(coada[coada[0]-1],coada[coada[0]],v[i])>0) --coada[0];
		coada[++coada[0]]=v[i];
	}
	freopen("infasuratoare.out","w",stdout);
	coada[++coada[0]]=origine;
	printf("%d\n",coada[0]-1);
	reverse(coada+1,coada+coada[0]+1);
	for(i=1;i<coada[0];i++)
	{
		printf("%lf %lf\n",X[coada[i]],Y[coada[i]]);
	}
	return 0;
}