Cod sursa(job #1540148)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 2 decembrie 2015 11:18:32
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct du{
    double x,y;}v[120111];
int i,n,curent,initial,start,poznoua,Re[120001],nr;
double Max;
bool viz[120001];
int main()
{
f>>n;
for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;
v[0].x=v[0].y=1000000000;
 for(int i=1;i<=n;i++)
        if (v[i].x<v[initial].x)
            initial=i;
start=1;
curent=initial;
   double last = 0;
    while(start!=0||initial!=curent){
                start=0;
                Re[++nr]=curent;
        Max=100000;
            for(i=1;i<=n;i++){
                if(i==curent||viz[i]==1)
                    continue;
                  double unghi = atan2((v[i].x -v[curent].x),v[i].y-v[curent].y);
                if (unghi < 0) unghi += 2* M_PI;
            unghi -= last;
            if (unghi < 0) unghi += 2 * M_PI;
                if (Max > unghi) {
                        Max= unghi;
                    poznoua = i;}
                    }
            last = atan2(-(v[curent].x- v[poznoua].x),-(v[curent].y - v[poznoua].y));
        if (last<0) last += 2 * M_PI;
        curent = poznoua;
        viz[curent] = 1;}
g<<nr<<'\n';
for(i=nr;i>=1;i--)
        g<<v[Re[i]].x<<" "<<v[Re[i]].y<<'\n';;

    return 0;
}