Cod sursa(job #1363046)

Utilizator ooptNemes Alin oopt Data 26 februarie 2015 17:59:17
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
// infasuratoare
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>

#define pb push_back
#define NMax 120005

using namespace std;

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

int n;
double X[NMax], Y[NMax];
int init = 1;
bool ch[NMax];
vector<int> sol;

void read() {
    f>>n;
    for (int i=1;i<=n;i++) {
        f>>X[i]>>Y[i];
        if (X[i] < X[init])
            init = i;
    }
}

void bl(double &angle) {
    if (angle < 0)
        angle += 2*M_PI;
}

void solve() {
    int cur = init;
    double last = 0;

    do {
        int bst = cur;
        double ma = 10000;
        sol.pb(cur);
        for (int i=1;i<=n;i++) {
            if (ch[i] || i == cur) continue;
            double unghi = atan2(X[i]-X[cur], Y[i]-Y[cur]);
            bl(unghi);
            unghi-=last;
            bl(unghi);
            if (ma > unghi) {
                ma = unghi;
                bst = i;
            }
        }

        last = ma;
        cur = bst;
        ch[cur] = true;
    } while (init != cur);
}

void output() {
    reverse(sol.begin(), sol.end());
    g<<sol.size()<<'\n';
    for (unsigned i=0;i<sol.size();i++)
        g<<fixed<<setprecision(12)<<X[sol[i]]<<' '<<Y[sol[i]]<<'\n';
}

int main() {

    read();
    solve();
    output();

    f.close(); g.close();
    return 0;
}