Cod sursa(job #1191372)

Utilizator andreiagAndrei Galusca andreiag Data 27 mai 2014 11:30:13
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
// naiv -- O(n^2)
#include <fstream>
#include <iostream>
#include <vector>
#include <iomanip>
#include <math.h>

using namespace std;
const int Nmax = 120005;

double X[Nmax], Y[Nmax];
char used[Nmax];
vector<int> hull;


int main()
{
    ifstream f ("infasuratoare.in");
    ofstream g ("infasuratoare.out");
    
    int N;
    f >> N;
    for (int i = 0; i < N; i++)
        f >> X[i] >> Y[i];

    int start = 0;
    for (int i = 0; i < N; i++)
        if (X[start] > X[i] || (X[start] == X[i] && Y[start] > Y[i]))
            start = i;
    
    int cur = start;
    double last_angle = M_PI * 3/2;
    double current_angle = 0;
    
    while(hull.empty() || cur != start)
    {
        double best_angle = 1000;
        int candidate = -1;
        for (int i = 0; i < N; i++)
        {
            if (i == cur || used[i]) continue;
            double new_angle = atan2(Y[i] - Y[cur], X[i] - X[cur]);
            if (new_angle < 0)
                new_angle += 2*M_PI;
            double angle = new_angle - last_angle;
            if (angle < 0)
                angle += 2*M_PI;
            if (angle < best_angle)
            {
                best_angle = angle;
                candidate = i;
                current_angle = new_angle;
            }
        }
        
        last_angle = current_angle;
        hull.push_back(candidate);
        used[candidate] = 1;
        cur = candidate;
        
    }
    g << setprecision(16) << hull.size() << '\n';
    //g << setprecision(16) << X[hull.back()] << ' ' << Y[hull.back()] << '\n';
    //hull.pop_back();
    for (int i: hull)
        g << X[i] << ' ' << Y[i] << '\n';

    return 0;
}