Cod sursa(job #1569219)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 15 ianuarie 2016 10:10:24
Problema Gradina Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>
#include <cmath>
using namespace std;
#define INF LLONG_MAX
#define Nmax 250
using ll = long long;
using pct = struct {int x, y, p;};

int n;
ll difMin;
int S[Nmax];
pct v[Nmax], x[Nmax + 5], y[Nmax + 5];
vector< bool > sol(Nmax), aux(Nmax);

int read() ;
void write() ;
void check(int, int) ;
ll cross_product(pct, pct, pct) ;
bool CMP(pct a, pct b)
{
    return cross_product(v[0], a, b) < 0;
}

int main()
{
    int i, j, pMin;
    
    pMin = read();
    swap(v[0], v[pMin]);
    sort(v + 1, v + n, CMP);
    
    for(difMin = INF, i = 0; i < n; ++i)
        for(j = 0; j < n; ++j)
            if(i != j) check(i, j);
    
    write();
    
    return 0;
}

int read()
{
    int i, pMin;
    ifstream fin("gradina.in");
    
    fin >> n;
    for(pMin = i = 0; i < n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        v[i].p = i;
        if(v[i].x < v[pMin].x || (v[i].x == v[pMin].x && v[i].y < v[pMin].y))
            pMin = i;
    }
    
    fin.close();
    
    return pMin;
}

void write()
{
    ofstream fout("gradina.out");
    
    fout << difMin / 2 << '.' << (difMin % 2 ? 5 : 0) << '\n';
    
    for(int i = 0; i < n; ++i)
        if(sol[i]) fout << 'V';
        else fout << 'I';
    fout << '\n';
    
    fout.close();
}

void check(int p1, int p2)
{
    int i, n1, n2;
    ll a1, a2, dif;
    
    if(p1 < p2)
    {
        for(n1 = n2 = 0, i = 0; i < n; ++i)
            if(i == p1 || cross_product(v[p1], v[p2], v[i]) > 0)
                x[++n1] = v[i], aux[v[i].p] = true;
            else if(i == p2 || cross_product(v[p1], v[p2], v[i]) < 0)
                y[++n2] = v[i], aux[v[i].p] = false;
    }
    else
    {
        for(n1 = n2 = 0, i = 0; i < n; ++i)
            if(i == p1 || cross_product(v[p1], v[p2], v[i]) < 0)
                x[++n1] = v[i], aux[v[i].p] = true;
            else if(i == p2 || cross_product(v[p1], v[p2], v[i]) > 0)
                y[++n2] = v[i], aux[v[i].p] = false;
    }
    
    if(sol[0] == true) for(i = 0; i < n; ++i) sol[i] = !sol[i];
    
    if(n1 < 3 || n2 < 3) return;
    
    for(i = 1; i <= n1 - 2; ++i)
        if(cross_product(x[i], x[i + 1], x[i + 2]) > 0)
            return;
    
    for(i = 1; i <= n2 - 2; ++i)
        if(cross_product(y[i], y[i + 1], y[i + 2]) > 0)
            return;
    
    
    x[0] = x[n1]; x[n1 + 1] = x[1];
    for(a1 = 0, i = 1; i <= n1; ++i)
        a1 += 1LL * x[i].x * (x[i + 1].y - x[i - 1].y);
    if(a1 < 0) a1 = -a1;
    
    y[0] = y[n2]; y[n2 + 1] = y[1];
    for(a2 = 0, i = 1; i <= n2; ++i)
        a2 += 1LL * y[i].x * (y[i + 1].y - y[i - 1].y);
    if(a2 < 0) a2 = -a2;
    
    dif = a1 < a2 ? a2 - a1 : a1 - a2;
    if(dif < difMin)
    {
        difMin = dif;
        sol = aux;
    }
    else if(dif == difMin && sol > aux)
        sol = aux;
}

ll cross_product(pct a, pct b, pct c)
{
    return 1LL * (b.x - a.x) * (c.y - a.y)
            - 1LL * (b.y - a.y) * (c.x - a.x);
}