Cod sursa(job #1456154)

Utilizator retrogradLucian Bicsi retrograd Data 29 iunie 2015 21:50:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long var;

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

typedef pair<double, double> Point;
#define x first
#define y second

#define det(A, B, C) (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)

set<Point> Up, Dw;

bool bad(set<Point> &Set, set<Point>::iterator it) {
    if(it == Set.begin()) return false;
    if(++it == Set.end()) return false;

    auto C = *it--, B = *it--, A = *it;
    return det(A, B, C) <= 0;
}

void ins(Point P, set<Point> &Set) {

    auto it = Set.insert(P).x;
    if(Set.size() <= 2) return;
    if(bad(Set, it)) {Set.erase(it); return;}

    auto chk_succ = [&Set, &it]() {
        auto succ = it; succ++;
        if(succ == Set.end()) return;

        while(bad(Set, succ)) {
            auto aux = succ++;
            Set.erase(aux);
        }
    };

    auto chk_pred = [&Set, &it]() {
        if(it == Set.begin()) return;
        auto pred = it; pred--;

        while(bad(Set, pred)) {
            auto aux = pred--;
            Set.erase(aux);
        }
    };

    chk_succ();
    chk_pred();
}

void insertPoint(double a, double b) {
    ins(Point(a, b), Up);
    ins(Point(-a, -b), Dw);
}

void Afis() {
    vector<Point> UpV(Up.begin(), Up.end());
    vector<Point> DwV(Dw.begin(), Dw.end());

    UpV.pop_back();
    DwV.pop_back();

    fout<<fixed<<setprecision(10)<<UpV.size()+DwV.size()<<'\n';
    for(auto P : UpV) {fout<<P.x<<" "<<P.y<<'\n';}
    for(auto P : DwV) {fout<<-P.x<<" "<<-P.y<<'\n';}

}

int main() {
    var n;
    double x, y;

    fin>>n;

    while(n--) {
        fin>>x>>y;
        insertPoint(x, y);
    }
    Afis();
    return 0;
}