Cod sursa(job #1658382)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 21 martie 2016 14:03:17
Problema Gradina Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

static constexpr char lookup[] = "IV";

using ll = long long;

struct punct{
    ll x, y;
    int ind;
};

bool left_turn(const ll x1, const ll y1, const ll x2, const ll y2, const ll x3, const ll y3){
    return x1 * y2 + x2 * y3 + x3 * y1 > x1 * y3 + x2 * y1 + x3 * y2;
}

bool left_turn(const punct a, const punct b, const punct c){
    return left_turn(a.x, a.y, b.x, b.y, c.x, c.y);
}

bool check_convex(const vector<punct>& pts){
    const int n = pts.size();
    if(n == 2){
        return true;
    }
    bool good = true;
    for(int i = 0, j = 1, k = 2; i < n; ++i, ++j, ++k, j %= n, k %= n){
        good = (good && left_turn(pts[i], pts[j], pts[k]));
    }
    return good;
}

double area(const punct& a, const punct& b){
    return (double)((a.x - b.x) * (a.y + b.y)) / 2.0;
}

double area(const vector<punct>& pts){
    const int n = pts.size();
    double rez = 0;
    for(int i = 0, j = 1; i < n; ++i, ++j, j %= n){
        rez += area(pts[i], pts[j]);
    }
    return abs(rez);
}

void put_in_order(vector<punct>& pts){
    vector<punct> under, over;
    for(int i = 1; i < pts.size() - 1; ++i){
        (left_turn(pts.front(), pts.back(), pts[i]) ? over : under).push_back(pts[i]);
    }
    vector<punct> rez = {pts[0]};
    copy(begin(under), end(under), back_inserter(rez));
    rez.push_back(pts.back());
    reverse_copy(begin(over), end(over), back_inserter(rez));
    pts = rez;
}

void do_for_pair(const vector<punct>& pts, const int a, const int b, double& best, vector<bool>& rez){
    const int n = pts.size();
    vector<punct> ion, vasile;
    vector<bool> dist(n, false);
    for(int i = 0; i < n; ++i){
        const bool tmp = (i == a) || (i != b && left_turn(pts[a], pts[b], pts[i]));
        (tmp ? vasile : ion).push_back(pts[i]);
        dist[pts[i].ind] = tmp;
    }

    if(ion.size() == 1 || vasile.size() == 1){
        return;
    }

    put_in_order(ion), put_in_order(vasile);

    if(!check_convex(ion) || !check_convex(vasile)){
        return;
    }

    const double cur = abs(area(ion) - area(vasile));

    if(cur < best || (cur == best && lexicographical_compare(begin(dist), end(dist), begin(rez), end(rez)))){
        best = cur;
        rez = dist;
    }
}

int main()
{
    ifstream f("gradina.in");
    ofstream g("gradina.out");
    int n;
    f >> n;

    vector<punct> pts(n);
    for(int i = 0; i < n; ++i){
        f >> pts[i].x >> pts[i].y;
        pts[i].ind = i;
    }
    sort(begin(pts), end(pts), [](const punct& a, const punct& b){ return a.x < b.x; });

    double best = 1e18;
    vector<bool> rez(n);

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i != j){
                do_for_pair(pts, i, j, best, rez);
            }
        }
    }

    g << fixed << setprecision(1) << best << '\n';

    for(const auto x : rez){
        g << lookup[x];
    }

    return 0;
}