Cod sursa(job #1673942)

Utilizator MaraaMMihali Mara MaraaM Data 4 aprilie 2016 11:28:11
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>

#define max_n 120000

using namespace std;

vector <int> v;
vector <int>::iterator it;
double x[max_n],y[max_n];
double u,z,unghi;
int i,in,n,c,poz,h;
bool ok,use[max_n];

int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d\n",&n);
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&x[i],&y[i]);
	in=1; // indicele punctului de plecare
	for (i=2; i<=n; i++)
		if (x[i]<x[in]) in=i; //alegem cel mai de jos punct
	c=in; // c=indicele punctului curent
	u=0;
	ok=true;
	while (ok || in!=c)
	{
		ok=false;
		v.push_back(c); //se retine in v(vectorul punctelor de pe infasuratoare) elementul curent
		poz=c;
		z=10000;
		for (i=1; i<=n; i++) /* se gaseste cel mai mare unghi facut de dreapta suport cu unul dintre punctele neselectate pe infasuratoare
S-a utilizat functia predefinita "atan2"(arctg(y/x), in intervalul [-pi,+pi] rad ) */
		{
			if (use[i] || i==c) continue; //se pot utiliza doar punctele neaflate inca pe infasuratoare
				unghi=atan2((x[i]-x[c]),(y[i]-y[c]));
			if (unghi<0) unghi+=2 * M_PI;
			unghi-=u;
			if (unghi<0) unghi+=2 * M_PI;
			if (z>unghi) {
				z=unghi;
				poz=i;
			}
		}
		u=atan2(-(x[c]-x[poz]),-(y[c]-y[poz]));
		if (u<0) u+=2 * M_PI;
		c=poz; // se actualizeaza pozitia curenta
		use[c]=true; //se valideaza utilizarea punctului curent

	}
	reverse(v.begin(),v.end()); //pentru ordine trigonometrica
	h=v.size(); //nr de puncte de pe infasuratoare
	printf("%d\n",h);
	for (i=0; i<h; i++)
	printf("%lf %lf\n",x[v[i]],y[v[i]]);
	return 0;
}