Cod sursa(job #889465)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 24 februarie 2013 15:32:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
#include<cmath>
#define EPS 0.000001
using namespace std;
int n,m,A[120010],P0;
double X[120010],Y[120010];

inline double Dist(int i)
{
	return sqrt((X[i]-X[P0])*(X[i]-X[P0])+(Y[i]-Y[P0])*(Y[i]-Y[P0]));
}

inline bool Sortare(int i,int j)
{
	if(abs((X[i]-X[P0])*(Y[j]-Y[P0])-(X[j]-X[P0])*(Y[i]-Y[P0]))<=EPS)
		return Dist(i)>Dist(j);
	return (X[i]-X[P0])*(Y[j]-Y[P0])<(X[j]-X[P0])*(Y[i]-Y[P0]);
}

long double Intoarcere(int A,int B,int C)
{
	return (long double)(X[A]*Y[B]+X[B]*Y[C]+X[C]*Y[A]-X[C]*Y[B]-X[B]*Y[A]-X[A]*Y[C]);
}

int main()
{
	int i;
	freopen("infasuratoare.in","r",stdin);
	scanf("%d",&n);
	//determin la citire punctul cel mai din stanga,cel mai de jos in caz de egalitate
	X[0]=Y[0]=2000000000.0;
	P0=0;
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf",X+i,Y+i);
		if(X[i]<X[P0] || (X[i]==X[P0] && Y[i]<Y[P0]))
			P0=i;
	}
	//selectez toate punctele in afara de P0 pentru a le sorta
	for(i=1;i<P0;i++)
		A[i]=i;
	for(i=P0+1;i<=n;i++)
		A[i-1]=i;
	m=n-1;
	//le sortez
	sort(A+1,A+m+1,Sortare);
	//bag punctele in stiva
	int St[120010],vf=0;
	St[vf]=P0;
	for(i=1;i<=m;i++)
	{
		while(vf>=1 && Intoarcere(St[vf-1],St[vf],A[i])>0)
		{
			//daca punctul curent face cu ultimele 2 puncte din stiva o intoarcere spre dreapta
			//atunci este scos din infasuratoare punctul din varful stivei
			vf--;
		}
		St[++vf]=A[i];
	}
	//afisez punctele de pe infasuratoarea convexa
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",vf+1);
	for(i=vf;i>=0;i--)
		printf("%lf %lf\n",X[St[i]],Y[St[i]]);
	return 0;
}