Cod sursa(job #2438851)

Utilizator bojemoiRadu Mamaliga bojemoi Data 14 iulie 2019 07:22:18
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>



using namespace std;



ifstream fin("infasuratoare.in");

ofstream fout("infasuratoare.out");



vector <int> v;

int n, pm;

double x[120004], y[120004], mini = 1000000004;

bool viz[120004];



int main(){

    fin>>n;

    for(int i=1; i<=n; ++i){

        fin>>x[i]>>y[i];

        if(x[i]<mini){ mini = x[i]; pm = i; }

        if(x[i]==mini && y[i]<y[pm]) pm = i;

    }



    double last=0;

    bool mov=1;

    int cur = pm;

    do{

        mov = 0;

        v.push_back(cur);

        int np=cur;

        double ma = 100000;

        for(int i=1; i<=n; ++i){

                if(viz[i] || i==cur) continue;

                double unghi = atan2(x[i]-x[cur],y[i]-y[cur]);

                if(unghi<0) unghi+=2*M_PI;

                unghi-=last;

                if(unghi<0) unghi+=2*M_PI;

                if(ma>unghi){ma = unghi; np = i;}

        }

        last = atan2(-(x[cur]-x[np]),-(y[cur]-y[np]));

        if(last<0) last+=2*M_PI;

        cur = np;

        viz[cur] = 1;

    }while(cur!=pm);

    fout<<v.size()<<'\n';

    for(int i=v.size()-1; i>=0; --i) fout<<std::fixed<<std::setprecision(12)<<x[v[i]]<<" "<<y[v[i]]<<'\n';



    return 0;

}