Cod sursa(job #672902)

Utilizator kitzTimofte Bogdan kitz Data 3 februarie 2012 13:32:21
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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;
}