Cod sursa(job #449275)

Utilizator SigoMihai Popescu Sigo Data 6 mai 2010 07:54:10
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>
#include<math.h>
#include<fstream.h>

#define maxn 1200

double VECT[maxn];
double X[maxn],Y[maxn];
double N,VER[maxn];

int main()
{
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>N;
	X[0] = 1000000000;
	Y[0] = 1000000000;
	for(int i = 1;i <= N; i++)
		f>>X[i]>>Y[i];
	int punct_initial = 0;
	int cur = 0;
	int move = 1;
	int dim = 0;
	for(i = 1;i <= N; i++)
		if (X[i] < X[punct_initial]) punct_initial = i;
	cur = punct_initial;
	double last = 0;
	while(move || punct_initial != cur)
	{
		move = 0;
		dim++; VECT[dim]=cur;
		double ma = 10000;
		int poznoua = cur;
		for(int i = 1;i <= N; i++)
		{
			if (VER[i] || i == cur) continue;
			double 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; poznoua = i;}
		}
		last = atan2(-(X[cur] - X[poznoua]),-(Y[cur] - Y[poznoua]));
		if (last < 0) last += 2 * M_PI;
		cur = poznoua;
		VER[cur] = 1;
	}
	g<<dim<<' ';
	for(i=dim; i>=1; i--) g<<X[VECT[i]]<<' '<<Y[VECT[i]]<<endl;
	return 0;
}