Cod sursa(job #2439294)

Utilizator bluestorm57Vasile T bluestorm57 Data 15 iulie 2019 16:22:02
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
# define M_PI           3.14159265358979323846

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int NMAX = 120005;
const int inf = 1000000006;
int n,initial;
bool viz[NMAX];
struct point{
    double x,y;
}v[NMAX], posmin;
vector<int> Vector;

int main(){
    int i;
    f >> n;
    posmin.x = inf;
    for(i = 1 ; i <= n ; i++){
        f >> v[i].x >> v[i].y;
        if(v[i].x < posmin.x){
            initial = i;
            posmin = v[i];
        }else
            if(v[i].x == posmin.x && v[i].y < posmin.y){
                initial = i;
                posmin = v[i];
            }
    }

    bool move = 1;
    int actual = initial;
    double last = 0;
    while(move || actual != initial){
        move = 0;
        Vector.push_back(actual);
        int newpos = actual;
        double ma = 10005;

        for(i = 1 ; i <= n ; i++){
            if(viz[i] || i == actual)
                continue;
            double unghi = atan2(v[i].x - v[actual].x , v[i].y - v[actual].y);
            if(unghi < 0)
                unghi += 2 * M_PI;
            unghi -= last;
            if(unghi < 0)
                unghi += 2 * M_PI;
            if(unghi < ma){
                ma = unghi;
                newpos = i;
            }
        }

        last = atan2(v[newpos].x - v[actual].x, v[newpos].y - v[actual].y);
        if(last < 0)
            last += 2 * M_PI;
        actual = newpos;
        viz[actual] = 1;
    }

    reverse(Vector.begin(), Vector.end());

    g << Vector.size() << "\n";
    for(auto it: Vector)
        g << fixed << setprecision(6) << v[it].x << " " << v[it].y << "\n";

    return 0;
}