Cod sursa(job #588436)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 mai 2011 23:24:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

typedef struct
{
	long double x;
	long double y;
}
Coordonate;

long const Infinit=2000000000;
Coordonate P, Puncte[120001];
long N, PMin, Stiva[120001], In[120001], K;

void Read ()
{
	ifstream fin ("infasuratoare.in");
	long i;
	Coordonate Aux;
	P.x=Infinit;
	P.y=Infinit;
	fin >> N;
	for (i=1; i<=N; i++)
	{
		fin >> Puncte[i].x >> Puncte[i].y;
		if ((Puncte[i].y<P.y)||((Puncte[i].y==P.y)&&(Puncte[i].x<P.x)))
		{
			P=Puncte[i];
			PMin=i;
		}
	}
	Aux=Puncte[1];
	Puncte[1]=Puncte[PMin];
	Puncte[PMin]=Aux;
	fin.close ();
}

void Type ()
{
	ofstream fout ("infasuratoare.out");
	long i;
	fout << K-1 << "\n";
	for (i=1; i<K; i++)
	{
		fout << Puncte[Stiva[i]].x << " " << Puncte[Stiva[i]].y << "\n";
	}
	fout.close ();
}

bool cmp(Coordonate a, Coordonate b)
{
	if (((a.x-P.x)*(b.y-P.y))>((a.y-P.y)*(b.x-P.x)))
	{
		return true;
	}
	else
	{
		return false;
	}
}

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

int main ()
{
	long i, t=1;
	Read ();
	sort (Puncte+2, Puncte+N+1, cmp);
	Stiva[1]=1;
	Stiva[2]=2;
	K=2;
	In[2]=1;
	i = 2;
	while(!In[1])
	{
		while(In[i])
		{
			if(i == N)
				t = -1;
			i += t;
		}
		while(K > 1 && semn(Puncte[Stiva[K]], Puncte[Stiva[K - 1]], Puncte[i]) > 0)
			In[Stiva[K--]] = 0;
		Stiva[++K] = i;
		In[i] = 1;
	}
	Type ();
	return 0;
}