Cod sursa(job #1373560)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 4 martie 2015 19:30:59
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>

#define NN 120008
#define PI 3.14159265

using namespace std;

struct nod{
double x;
double y;
}a[NN];

vector <int> c;
vector <int>::iterator it;
double unghi,maxu,u;
bool ok,use[NN];

int n,o,i,start,poz;

int main()
{
freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
scanf("%d",&n);

o=1;
for(i=1;i<=n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
if (a[i].x<a[o].x)o=i;
else if (a[i].x==a[o].x && a[i].y<a[o].y)o=i;
}
start=o;
ok=true;



while(ok || start!=o){
ok=false;
c.push_back(o);
maxu=10000;

for(i=1;i<=n;i++)
if(use[i]==false && i!=o){
 unghi=atan2((a[i].x-a[o].x),(a[i].y-a[o].y));
 if (unghi<0)unghi+= 2*PI;
 unghi-=u;
 if(unghi<0)unghi+= 2*PI;
 if (maxu>unghi){
  poz=i;
  maxu=unghi;
 }
}
u=atan2(-(a[o].x-a[poz].x),-(a[o].y-a[poz].y));
if (u<0)u+=2*PI;
o=poz;
use[o]=true;
}
printf("%d\n",c.size());
reverse(c.begin(),c.end());
for(it=c.begin();it!=c.end();++it)
printf("%f %f\n",a[*it].x,a[*it].y);


return 0;
}