Cod sursa(job #544829)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 martie 2011 11:04:41
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 120005

int N, O, S[DIM];
struct punct { double x, y; } P[DIM], T;

int cmp (punct a, punct b)
{
	return a.y * b.x < a.x * b.y;
}

int determ3 (punct a, punct b, punct c)
{
	return (b.x*c.y + a.x*b.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y) < 0;	
}

void citire ()
{
	scanf ("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf ("%lf%lf", &P[i].x, &P[i].y);
		if (P[O].y > P[i].y)
			O = i;
	}
}

void sortare ()
{
	punct aux = P[O]; P[O] = P[0]; P[0] = aux;
	T = P[0];
	for (int i = 0; i < N; i++)
		P[i].x -= T.x, P[i].y -= T.y;
	sort (P + 1, P + N, cmp);
}
	
void infasoara ()
{
	S[++S[0]] = 0;
	S[++S[0]] = 1;
	
	for (int i = 2; i < N; i++)
	{
		while (determ3 (P[S[S[0] - 1]], P[S[S[0]]], P[i]))
			S[0] --;
		S[++S[0]] = i;
		
	}
}

void afisare ()
{
	printf ("%d\n", S[0]);
	for (int i = 1; i <= S[0]; i++)
		printf ("%lf %lf\n", P[S[i]].x + T.x, P[S[i]].y + T.y);
}

int main ()
{
	freopen ("infasuratoare.in", "r", stdin);
	freopen ("infasuratoare.out", "w", stdout);
	
	citire ();
	sortare ();
	infasoara ();
	afisare ();
	
	return 0;
}