Cod sursa(job #615484)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 9 octombrie 2011 20:02:36
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<=n;i++)
	{
		if(i!=P0)
			A[++m]=i;
	}
	//le sortez
	sort(A+1,A+m+1,Sortare);
	//bag punctele in stiva
	int nr;
	vector <int> St;
	St.push_back(P0);
	nr=0;
	for(i=1;i<=m;i++)
	{
		while(St.size()>=2 && Intoarcere(St[nr-1],St[nr],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
			St.pop_back();
			nr--;
		}
		St.push_back(A[i]);
		nr++;
	}
	//afisez punctele de pe infasuratoarea convexa
	freopen("infasuratoare.out","w",stdout);
	printf("%d\n",St.size());
	reverse(St.begin(),St.end());
	for(i=0;i<=nr;i++)
		printf("%lf %lf\n",X[St[i]],Y[St[i]]);
	return 0;
}