Cod sursa(job #1528818)

Utilizator enedumitruene dumitru enedumitru Data 20 noiembrie 2015 04:40:21
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");
const int Nmax=120000;
float X[Nmax],Y[Nmax];
int N,H,Viz[Nmax],Q[Nmax];
int main()
{   f>>N;
    int i;
    X[0]=Y[0]=1000000000;
    for(i=1;i<=N;++i) f>>X[i]>>Y[i];
    int Pinitial=0;
    for(i=1;i<=N;++i)
        if(X[i]<X[Pinitial]) Pinitial=i;
    int w=1,Pcurent=Pinitial;
    float last=0;
    while(w || Pinitial != Pcurent)
    {   w=0;
        Q[++H]=Pcurent;
        float Umax=10000;
        int Pmax=Pcurent;
        for(i=1;i<=N;++i)
            if(!Viz[i] and i!=Pcurent)
            {   float unghi=atan2((X[i]-X[Pcurent]),Y[i]-Y[Pcurent]);
                if(unghi<0) unghi+=2*M_PI;
                unghi-=last;
                if(unghi<0) unghi+=2*M_PI;
                if(Umax>unghi) {Umax=unghi; Pmax= i;}
            }
        last=atan2(-(X[Pcurent]-X[Pmax]),-(Y[Pcurent]-Y[Pmax]));
        if(last<0) last+=2*M_PI;
        Pcurent=Pmax;
        Viz[Pcurent]=1;
    }
    reverse(Q+1,Q+H+1);
    g<<H<<'\n';
    for(i=1;i<=H;++i)g<<fixed<<setprecision(6)<<X[Q[i]]<<' '<<Y[Q[i]]<<'\n';
    g.close(); return 0;
}