Cod sursa(job #876422)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 11 februarie 2013 20:21:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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;
		printf("1");
		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;
}