Cod sursa(job #1658423)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 21 martie 2016 15:02:23
Problema Gradina Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 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;

ll absolute(const ll vodka){
	return (vodka < 0 ? -vodka : vodka);
}
 
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-y3) + x2 * (y3-y1) + x3 * (y1-y2) > 0;
}
 
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; k < n; ++i, ++j, ++k){
        good = (good && left_turn(pts[i], pts[j], pts[k]));
    }
    return good && left_turn(pts[n-2], pts[n-1], pts[0]) && left_turn(pts[n-1], pts[0], pts[1]);
}
 
ll area(const punct& a, const punct& b){
    return (a.x - b.x) * (a.y + b.y);
}
 
ll area(const vector<punct>& pts){
    const int n = pts.size();
    ll rez = 0;
    for(int i = 0, j = 1; j < n; ++i, ++j){
        rez += area(pts[i], pts[j]);
    }
    return absolute(rez + area(pts[n-1], pts[0]));
}
 
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, ll& 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 ll cur = absolute(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; });
 
    ll best = 1000000000000000000ll;
    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) << (double)best/2.0 << '\n';
 
    for(const auto x : rez){
        g << lookup[x];
    }
    return 0;
}