Cod sursa(job #295023)

Utilizator cotofanaCotofana Cristian cotofana Data 2 aprilie 2009 22:06:16
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <math.h>
#define dim 120100

using namespace std;

vector<int> v;
int n, fol[dim], in;
double x[dim], y[dim];

int main()
{
	int i, cur, move, pozn;
	double last, unghi, ma;
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d\n", &n);
	x[0]=10e11;
	y[0]=10e11;
	in=0;
	for (i=1; i<=n; i++)
	{
		scanf("%lf %lf\n", &x[i], &y[i]);
		if (x[i]<x[in] || (x[i]==x[in] && y[i]<y[in])) in=i;
	}
	move=1;
	cur=in;
	last=0;
	while (move || cur!=in)
	{
		move=0;
		v.push_back(cur);
		pozn=cur;
		ma=10000;
		for (i=1; i<=n; i++)
		{
			if (fol[i] || i==cur) continue;
			unghi=atan2(x[i]-x[cur], y[i]-y[cur]);
			if (unghi<0) unghi+=2*M_PI;
			unghi-=last;
			if (unghi<0) unghi+=2*M_PI;
			if (ma>unghi)
			{
				ma=unghi;
				pozn=i;
			}
		}
		last=atan2(x[pozn]-x[cur], y[pozn]-y[cur]);
		if (last<0) last+=2*M_PI;
		cur=pozn;
		fol[cur]=1;
	}
	reverse(v.begin(), v.end());
	printf("%d\n", v.size());
	for (i=0; i<v.size(); i++) printf("%lf %lf\n", x[v[i]], y[v[i]]);
	return 0;
}