Cod sursa(job #2011743)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 august 2017 01:22:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <bits/stdc++.h>
using namespace std;

// fiecare punct e reprezentat de un numar complex
using cd = complex<double>;

// cross(x, y) = produsul vector a vectorilor de pozitie a lui x si y
// efectiv, e util pentru ca, pentru 3 puncte a, b, c,
// notand CP = cross(a-b, c-b)
// CP < 0 daca si numai daca ne a->b->c e o intoarcere "la dreapta"
// CP == 0 daca si numai daca a, b, c colineare
// CP > 0 daca si numai daca a->b->c e o intoarcere "la stanga"
double cross(const cd& x, const cd& y){
    return imag(x * conj(y)); }

// functia asta va crea o jumatate din infasuratoare
// astfel: daca v e sortat de la stanga la dreapta, geometric, va returna jumatatea inferioara a infasuratorii
// invers, atunci partea superioara
// folosind ideea de stiva de la scanarea graham
vector<cd> half_convex_hull_2d(const vector<cd>& v){
    vector<cd> rez;
    for(const auto x : v){
        // rez.rbegin()[x] = al x-lea element din spatele lui rez
        while(rez.size() >= 2 && cross(rez.rbegin()[0] - rez.rbegin()[1], x - rez.rbegin()[1]) > 0)
            rez.pop_back();
        rez.push_back(x); }
    return rez; }

vector<cd> convex_hull_2d(vector<cd> v){
    // sortam mai intai dupa x, apoi dupa y
    sort(begin(v), end(v), [&](const cd& a, const cd& b){
        return make_pair(real(a), imag(a)) < make_pair(real(b), imag(b)); });
    // facem jumatatea inferioara
    auto h1 = half_convex_hull_2d(v);

    // facem jumatatea superioara
    reverse(begin(v), end(v));
    auto h2 = half_convex_hull_2d(v);

    // scoatem primul si ultimul element, ambele dublate
    h1.pop_back();
    h2.pop_back();

    // imbinam rezultatele
    copy(begin(h2), end(h2), back_inserter(h1));
    return h1; }

int main(){
    cout << cross(1, cd { 0, 1}) << endl;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n;

    f >> n;
    vector<cd> v(n);
    for(auto& p : v){
        double x, y;
        f >> x >> y;
        p = cd { x, y }; }
    auto rez = convex_hull_2d(v);
    g << rez.size() << '\n';
    g << fixed << setprecision(6);
    for(const auto p : rez) g << real(p) << ' ' << imag(p) << '\n';
    return 0; }