Cod sursa(job #1820296)

Utilizator alin1999Buzatu Alin alin1999 Data 1 decembrie 2016 15:49:51
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct a{
double x,y;
}
v[120001];
int i,n,viz[120001];
int infas[120001];
bool comparare (a lhs,a rhs){return lhs.y<rhs.y;}
bool comparare2 (a lhs,a rhs){return lhs.x<rhs.x;}
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>v[i].x>>v[i].y;
        int punct_initial=1;
        int curent=0;
       for(i=1;i<=n;++i)
        if(v[i].x<v[punct_initial].x)
            punct_initial=i;
        int miscare=1;
        curent=punct_initial;
        double last=0;int k=0;
        while(miscare||punct_initial!=curent)
        {
            miscare=0;
            double ma=10000;
            infas[++k]=curent;
            int poznoua=curent;
            for(i=1;i<=n;++i)
                {
                    if(viz[i]||i==curent)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(ma>unghi){ma=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;
        }
fout<<k<<"\n";
for(i=k;i>=1;--i)
    fout<<setprecision(6)<<fixed<<v[infas[i]].x<<" "<<v[infas[i]].y<<"\n";
    return 0;
}