Cod sursa(job #1362898)

Utilizator ooptNemes Alin oopt Data 26 februarie 2015 16:32:07
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <iomanip>

#define NMax 120005
#define pb push_back
 
using namespace std;
 
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

vector<int> VECT;
double X[NMax],Y[NMax];
int n,VER[NMax];

void bl(double &angle) {
    if (angle < 0)
        angle += 2 * M_PI;
}
 
int main() {
    // Citire
    f>>n;
    for(int i = 1;i <= n; ++i) f>>X[i]>>Y[i];

    // Aflarea punctului initial, cel mai de jos din stanga punct
    int punct_initial = 1;
    for(int i = 1;i <= n; ++i)
        if (X[i] < X[punct_initial]) punct_initial = i;
    int cur = punct_initial;
    double last = 0;
    
    do {
        //cout<<last<<endl;
        VECT.pb(cur);
        double ma = 10000;
        int poznoua = cur;
        for(int i = 1;i <= n; ++i) {
            if (VER[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;
                poznoua = i;
            }
        }
        last = atan2(X[poznoua]-X[cur],Y[poznoua]-Y[cur]);
        bl(last);
        cur = poznoua;
        VER[cur] = 1;
    } while (punct_initial != cur);

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