Cod sursa(job #588440)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 mai 2011 23:35:29
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 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[120100];
long N, PMin, Stiva[120100], In[120100], 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;
	Read ();
	sort (Puncte+2, Puncte+N+1, cmp);
	Stiva[1]=1;
	Stiva[2]=2;
	K=2;
	In[1]=1;
	In[2]=1;
	i=2;
	while(i<=N)
	{
		i++;
		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;
}