Cod sursa(job #889596)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 24 februarie 2013 16:43:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<fstream>
#include<cmath>
#define EPS 0.000001
using namespace std;
int n,P0,vf;
struct Punct{double x,y;};
Punct P[120010],St[120010];

inline double Dist(Punct A)
{
	return sqrt((A.x-P[1].x)*(A.x-P[1].x)+(A.y-P[1].y)*(A.y-P[1].y));
}

inline bool Sortare(Punct A,Punct B)
{
	if(abs((A.x-P[1].x)*(B.y-P[1].y)-(B.x-P[1].x)*(A.y-P[1].y))<=EPS)
		return Dist(A)<Dist(B);
	return (A.x-P[1].x)*(B.y-P[1].y)<(B.x-P[1].x)*(A.y-P[1].y);
}

inline double Intoarcere(Punct A,Punct B,Punct C)
{
	return (A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y);
}

int main()
{
	int i;
	freopen("infasuratoare.in","r",stdin);
	scanf("%d",&n);
	//determin la citire punctul cel mai de jos,cel mai din stanga in caz de egalitate
	P0=1;
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf",&P[i].x,&P[i].y);
		if(P[i].y<P[P0].y || (P[i].y==P[P0].y && P[i].x<P[P0].x))
			P0=i;
	}
	//selectez toate punctele in afara de P0 pentru a le sorta
	swap(P[1],P[P0]);
	sort(P+2,P+n+1,Sortare);
	//bag punctele in stiva
	St[vf]=P[1];
	for(i=2;i<=n;i++)
	{
		while(vf>=1 && Intoarcere(St[vf-1],St[vf],P[i])>=0.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]=P[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",St[i].x,St[i].y);
	return 0;
}