Cod sursa(job #588430)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 mai 2011 23:14:37
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 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], lev=1;

void Read ()
{
	ifstream fin ("infasuratoare.in");
	long i;
	Coordonate Aux;
	P.x=Infinit;
	P.y=Infinit;
	fin >> N;
	for (i=0; 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[0];
	Puncte[0]=Puncte[PMin];
	Puncte[PMin]=Aux;
	fin.close ();
}

void Type ()
{
	ofstream fout ("infasuratoare.out");
	long i;
	fout << lev << "\n";
	for (i=0; i<lev; 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;
	}
}

long double det(long double x1, long double y1, long double z1,long double x2, long double y2, long double z2, long double x3, long double y3, long double z3)
{
	return (x1*y2*z3 + x2*y3*z1 + x3*y1*z2 - z1*y2*x3 - z2*y3*x1 - z3*y1*x2);
}

int main ()
{
	long i;
	Read ();
	sort (Puncte+1, Puncte+N, cmp);
	Stiva[0]=0;
	Stiva[1]=1;
	for(i=2;i<=N;++i)
	{
		while(lev>=1 && det(Puncte[Stiva[lev-1]].x, Puncte[Stiva[lev-1]].y, 1.0f, Puncte[Stiva[lev]].x, Puncte[Stiva[lev]].y, 1.0f, Puncte[i].x, Puncte[i].y, 1.0f) < 0)
			--lev;
		Stiva[++lev] = i;
	}
	Type ();
	return 0;
}