Cod sursa(job #1608829)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 22 februarie 2016 13:37:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cmath>
#include <fstream>

using namespace std;

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

#define N 120001
#define INF 1000000001

int n;
double X[N], Y[N];
bool ok[N];
int V[N], nv = 0;

int main()
{
    in >> n;

    X[0] = INF;
    Y[0] = INF;
    int punct_initial = 0;
    for(int i = 1; i <= n; i++)
    {
        in >> X[i] >> Y[i];
        if(X[punct_initial] > X[i])
            punct_initial = i;
    }

    int punct_curent = punct_initial;
    bool porneste = 1;
    double unghi_anterior = 0;
    while(porneste || punct_curent != punct_initial)
    {
        porneste = 0;
        double unghi_optim = 10000;
        int punct_nou = punct_curent;
        V[++nv] = punct_curent;
        for(int i = 1; i <= n; i++)
        {
            if(ok[i] || i == punct_curent)
                continue;
            double unghi = atan2(X[i] - X[punct_curent], Y[i] - Y[punct_curent]);
            if(unghi < 0)
                unghi += 2 * M_PI;
            unghi -= unghi_anterior;
            if(unghi < 0)
                unghi += 2 * M_PI;

            if(unghi_optim > unghi)
            {
                unghi_optim = unghi;
                punct_nou = i;
            }
        }
        unghi_anterior = atan2((X[punct_nou] - X[punct_curent]), (Y[punct_nou] - Y[punct_curent]));
        if(unghi_anterior < 0)
            unghi_anterior += 2 * M_PI;
        punct_curent = punct_nou;

        ok[punct_curent] = 1;
    }

    out << nv << '\n';
    for(int i = nv; i >= 1; i--)
        out << X[V[i]] << ' ' << Y[V[i]] << '\n';
    return 0;
}