Cod sursa(job #588450)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 mai 2011 00:01:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

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

const int Infinit=2000000000;
Coordonate P, Puncte[120100];
int N, PMin, Stiva[120100], K;

void Read ()
{
	FILE *fin = fopen ("infasuratoare.in", "r");
	long i;
	Coordonate Aux;
	P.x=Infinit;
	P.y=Infinit;
	fscanf (fin, "%d\n", &N);
	for (i=1; i<=N; i++)
	{
		fscanf (fin, "%lf %lf", &Puncte[i].x, &Puncte[i].y);
		if ((Puncte[i].x<P.x)||((Puncte[i].x==P.x)&&(Puncte[i].y<P.y)))
		{
			P=Puncte[i];
			PMin=i;
		}
	}
	Aux=Puncte[1];
	Puncte[1]=Puncte[PMin];
	Puncte[PMin]=Aux;
	fclose (fin);
}

void Type ()
{
	FILE *fout = fopen ("infasuratoare.out", "w");
	long i;
	fprintf (fout, "%d\n", K-1);
	for (i=1; i<K; i++)
	{
		fprintf (fout, "%lf %lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);
	}
	fclose (fout);
}

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;
	i=2;
	while(i<=N)
	{
		i++;
		while(K > 1 && Semn(Puncte[Stiva[K]], Puncte[Stiva[K - 1]], Puncte[i]) > 0)
		{
			K--;
		}
		Stiva[++K] = i;
	}
	Type ();
	return 0;
}