Cod sursa(job #434611)

Utilizator s_holmesSherlock Holmes s_holmes Data 6 aprilie 2010 11:25:22
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#define pb push_back

const int maxn = 120000;

using namespace std;

vector<int> VECT;
double X[maxn],Y[maxn];
int N,VER[maxn];

int punct_initial = 0;
int cur;
int move = 1;
double last = 0;

void citire()
{
	scanf("%d\n",&N);
	X[0] = 1000000000;Y[0] = 1000000000;
	for(int i = 1;i <= N; ++i)
		scanf("%lf %lf\n",&X[i],&Y[i]);
}

void begin()
{
	for(int i = 1;i <= N; ++i)
		if (X[i] < X[punct_initial]) punct_initial = i;
	cur = punct_initial;
}

void scrie()
{
	reverse(VECT.begin(),VECT.end());
	printf("%d\n",VECT.size());
	for(unsigned int i = 0;i < VECT.size(); ++i)
		printf("%lf %lf\n",X[VECT[i]],Y[VECT[i]]);
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	citire();
	begin();
	while(move || punct_initial != cur)
	{
		move = 0;
		VECT.pb(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;
	}
	scrie();
	return 0;
}