Cod sursa(job #1882451)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 februarie 2017 11:02:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;

using cd = complex<double>;

double cross(const cd& a, const cd& b){
    return imag(conj(a) * b); }

bool is_left_turn(const cd& a, const cd& b, const cd& c){
    return cross(a-b, c-b) < -1e-12; }

template<typename T>
vector<cd> half_hull(T st, T dr){
    vector<cd> rez;
    for_each(st, dr, [&](const cd cur){
        while(rez.size() > 1 && !is_left_turn(rez[rez.size()-2], rez.back(), cur)) rez.pop_back();
        rez.push_back(cur); });
    return rez; }

vector<cd> full_hull(vector<cd>& v){
    sort(begin(v), end(v), [](const cd& a, const cd& b){
        return make_pair(real(a), imag(a)) < make_pair(real(b), imag(b)); });
    auto lower = half_hull(begin(v), end(v)),
        upper = half_hull(v.rbegin(), v.rend());
    upper.pop_back(), lower.pop_back();
    lower.insert(lower.end(), begin(upper), end(upper));
    return lower; }

int main(){
    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 = full_hull(v);
    g << rez.size() << '\n';
    for(const auto p : rez){
        g << fixed << setprecision(6) << real(p);
        g << ' ';
        g << fixed << setprecision(6) << imag(p);
        g << '\n'; }
    return 0; }