Cod sursa(job #1614933)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 februarie 2016 12:00:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
#include <iomanip>
#include <fstream>
using namespace std;

struct punct{
    double x, y;
    punct(){}
    punct(const double X, const double Y): x(X), y(Y){}
};

bool operator<(const punct& a, const punct& b){
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool is_left_turn(punct a, const punct& b, punct c){
    a.x -= b.x, c.x -= b.x;
    a.y -= b.y, c.y -= b.y;

    return a.x * c.y < a.y * c.x;
}

void construct_hull(const punct& rad, const vector<punct>& pts, deque<punct>& rez){
    rez.push_front(rad);
    rez.push_front(pts[0]);

    for(int i = 1; i < pts.size(); ++i){
        while(rez.size() > 1 && !is_left_turn(rez[1], rez[0], pts[i])){
            rez.pop_front();
        }
        rez.push_front(pts[i]);
    }
    reverse(rez.begin(), rez.end());
}

int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n;
    f >> n;
    vector<punct> v(n);
    for(int i = 0; i < v.size(); ++i){
        f >> v[i].x >> v[i].y; }
    sort(v.begin(), v.end());

    vector<punct> over, under;
    for(int i = 1; i < n-1; ++i){
        (is_left_turn(v[0], v[i], v[n-1]) ? under : over)
            .push_back(v[i]); }

    reverse(over.begin(), over.end());

    deque<punct> hull_over, hull_under;

    over.push_back(v[0]);
    under.push_back(v[n-1]);

    construct_hull(v[n-1], over, hull_over);
    construct_hull(v[0], under, hull_under);

    hull_over.pop_back();
    hull_under.pop_back();

    vector<punct> hull(hull_under.begin(), hull_under.end());
    hull.insert(hull.end(), hull_over.begin(), hull_over.end());

    g << hull.size() << '\n';
    g << fixed << setprecision(6);
    for(int i = 0; i < hull.size(); ++i){
        g << hull[i].x << ' ' << hull[i].y << '\n';
    }

    return 0;
}