Cod sursa(job #617654)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 15 octombrie 2011 10:08:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
int n,m,A[120010],P0;
double X[120010],Y[120010];

inline bool Sortare(int i,int j)
{
	return (double)(X[i]-X[P0])*(Y[j]-Y[P0])<(double)(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;
	ifstream fin("infasuratoare.in");
	fin>>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++)
	{
		fin>>X[i]>>Y[i];
		if(X[i]<X[P0] || (X[i]==X[P0] && Y[i]<Y[P0]))
			P0=i;
	}
	fin.close();
	//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;
	//vector <int> St;
	//St.push_back(P0);
	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);
	//reverse(St.begin(),St.end());
	for(i=vf;i>=0;i--)
		printf("%lf %lf\n",X[St[i]],Y[St[i]]);
	return 0;
}