Cod sursa(job #843771)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 28 decembrie 2012 13:33:30
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

ifstream fi ("infasuratoare.in");
ofstream fo ("infasuratoare.out");

const int dim = 120005;
int N, I[dim];
struct punct { double x, y; } P[dim];

double ariedet (punct p1, punct p2, punct p3)
{
	return (p1.x - p2.x) * (p3.y - p2.y) - (p3.x - p2.x) * (p1.y - p2.y);
}
int cmp (punct p2, punct p3)
{
	punct p1 = P[0];
	double d = ariedet (p1, p2, p3);
	if (d == 0)
	{
		d = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) - (p1.x-p3.x)*(p1.x-p3.x) - (p1.y-p3.y)*(p1.y-p3.y);
		return d > 0;
	}
	return d < 0;
}

void cit ()
{
	int i, best = 0;
	
	fi >> N;
	for (i = 0; i < N; i++)
	{
		fi >> P[i].x >> P[i].y;
		if (P[i].x < P[best].x || (P[i].x == P[best].x && P[i].y < P[best].y))
			best = i;
	}
	swap (P[0], P[best]);
	sort (P+1, P+N, cmp);
	for (i = 2; ariedet (P[0], P[1], P[i]) == 0; i++);
	for (int j = 1; j <= (i>>1); j++) swap (P[j], P[i-j]);
}

void inf ()
{
	I[++I[0]] = 0;
	I[++I[0]] = 1;
	for (int i = 2; i < N; i++)
	{
		while (I[0] > 2 && ariedet (P[I[I[0]-1]], P[I[I[0]]], P[i]) > 0)
			I[0]--;
		I[++I[0]] = i;
	}
}

void afi ()
{
	fo << I[0] << '\n';
	for (int i = 1; i <= I[0]; i++)
		fo << P[I[i]].x << ' ' << P[I[i]].y << '\n';
}

int main ()
{
	cit ();
	inf ();
	afi ();
	return 0;
}