Cod sursa(job #2809403)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 26 noiembrie 2021 22:02:41
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
/*
 * complexitate O(N * H), unde H = nr. de puncte pe laturile poligonului
 * avem in general O(Nlog2N), dar pt. teste facute inteligent putem ajunge la O(N ^ 2)
 */
#include <iostream>
#include <fstream>
#include <iomanip> // pt. setprecision
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int N = 1.2e5 + 1;
int n, punct_initial = 1, cur, poznoua;
double x[N], y[N], ma, unghi, last;
bool misca = 1, ver[N];
vector<int> ans;

int main(){
    f >> n;
    for(int i = 1; i <= n; i++)
        f >> x[i] >> y[i];

    f.close();
    for(int i = 2; i <= n; i++){
        if(x[i] > x[punct_initial]) // luam punctul cel mai din dreapta => cand calculam unghiul nu trebuie sa interschimbam axele x si y
            punct_initial = i;
    }

    cur = punct_initial;
    while(misca || punct_initial != cur){
        misca = 0; // doar la inceput si sfarsit vom trece prin punctul initial (nu il vom include a doua oara in vector)
        ans.push_back(cur);
        ma = 10000;
        poznoua = cur; // poznoua = urm. punct
        for(int i = 1; i <= n; i++){
            if(ver[i] || i == cur) // nu ne intereseaza puncte deja vizitate (verificam si i == cur pentru prima iteratie)
                continue;

            unghi = atan2(y[i] - y[cur], x[i] - x[cur]); // facem diferenta pt. ca atan2 returneaza unghiul facut cu centrul => consideram centrul sa fie punctul curent
            if(unghi < 0)
                unghi += 2 * M_PI;

            unghi -= last; // rotim axele
            if(unghi < 0)
                unghi += 2 * M_PI;

            if(ma > unghi)
                ma = unghi, poznoua = i;
        }

        last = atan2(y[poznoua] - y[cur], x[poznoua] - x[cur]);
        if(last < 0)
            last += 2 * M_PI;

        cur = poznoua;
        ver[cur] = 1;
    }

    g << fixed << setprecision(12) << ans.size() << '\n'; // fara setprecision nu merge (?)
    for(int i: ans)
        g << x[i] << ' ' << y[i] << '\n';

    g.close();
}