Cod sursa(job #1958067)

Utilizator igroitaGroita Igor igroita Data 7 aprilie 2017 23:18:13
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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;
    while(mov || cur!=pm){
        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;
    }
    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;
}