Cod sursa(job #700572)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 1 martie 2012 10:58:45
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int dim = 120005;
int N, I[dim], cadran2;
double X, Y;
struct pct { double x, y; } P[dim];

int cmp (pct a, pct b)
{
	if (a.x * b.y == b.x * a.y)
	{
		long long d1 = a.x * a.x + a.y * a.y;
		long long d2 = b.x * b.x + b.y * b.y;
		return d1 > d2;
	}
	return a.x * b.y > b.x * a.y;
}

double arie (double x1, double y1, double x2, double y2, double x3, double y3)
{
	return (x3 - x2)*(y1 - y2)-(x1 - x2)*(y3 - y2);
}

void cit ()
{
	int m = 0;
	fi >> N;
	for (int i = 0; i < N; i++)
	{
		fi >> P[i].x >> P[i].y;
		if (P[i].y < P[m].y)
			m = i;		
	}
	X = P[m].x;
	Y = P[m].y;
	P[m] = P[0];
	P[0].x = X;
	P[0].y = Y;
}

void prep1 ()
{
	for (int i = 0; i < N; i++)
	{
		P[i].x -= X;
		P[i].y -= Y;
		
		if (P[i].x < 0)
			cadran2 = 1;
	}	
	sort (P + 1, P + N, cmp);	
}

void infc ()
{
	I[0] = 2, I[1] = 0, I[2] = 1;
	for (int i = 2; i < N; i++)
	{
		while (I[0] > 2 && arie (P[I[I[0]-1]].x, P[I[I[0]-1]].y, P[I[I[0]]].x, P[I[I[0]]].y, P[i].x, P[i].y) < 0)
			I[0]--;
		I[++I[0]] = i;
	}
}

void prep2 ()
{
	for (int i = 0; i < N; i++)
	{
		P[i].x += X;
		P[i].y += Y;
	}	
}

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 ();
	prep1 ();
	infc ();
	prep2 ();
	afi ();
	return 0;
}