Cod sursa(job #1663455)

Utilizator mariusn01Marius Nicoli mariusn01 Data 25 martie 2016 23:53:29
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.3 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <bitset>
#define DIM 260
#define x first.first
#define y first.second
#define poz second
#define INF 1000000000000000LL

using namespace std;

pair< pair<int, int>, int > v[DIM], a, b, c;

long long det(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x2-x1) * (y3-y1) - (x3-x1) * (y2-y1);
}

vector <int> L, R;
deque <int> D, E;
int n, i, j, k, stanga, dreapta, ariaStanga, ariaDreapta;
long long minim;
bitset<DIM> F, G;
int poly(vector <int> L, deque<int> &D) {
    D.clear();
    D.push_back(L[0]);

    for (int i=1;i<L.size()-1;i++) {
        if (det( v[L[0]].x, v[L[0]].y, v[L[ L.size() - 1 ]].x, v[L[ L.size() - 1 ]].y , v[L[i]].x, v[L[i]].y) > 0){
            D.push_back( L[i] );
        } else {
            D.push_front( L[i] );
        }
    }
    D.push_back(L[ L.size()-1 ]);
    D.push_back( D.front() );

    //for (deque<int>::iterator it = D.begin(); it != D.end(); it++  )
    //    cout<<*it<<" ";
    //cout<<"\n";

    for (int i=0;i<D.size()-2;i++) {
        if (det( v[ D[i] ].x, v[ D[i] ].y, v[ D[i+1] ].x, v[ D[i+1] ].y, v[ D[i+2] ].x, v[ D[i+2] ].y) > 0) {
            return 0;
        }
    }
    return 1;
}

int aria(deque <int> D) {
    int rez = 0;
    while (1) {
    //for (i=0; i<D.size()-1; i++) {
        int a = D.front();
        D.pop_front();
        if (D.empty())
            break;
        int b = D.front();
        rez += det(0, 0, v[ a ].x, v[ a ].y, v[ b ].x, v[ b ].y);
    }
    return rez > 0 ? rez : -rez;
}

int modul(int a) {
    return a > 0 ? a : -a;
}

int main () {

//    a.x = 0;a.y = 0;b.x = 1;b.y = 0;c.x = 1;c.y = -1;
//    cout<<det(a.x, a.y, b.x, b.y, c.x, c.y);

    ifstream fin ("gradina.in");
    ofstream fout("gradina.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i].x>>v[i].y;
        v[i].poz = i;
    }

    sort(v+1, v+n+1);
    minim = INF;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) {
            if (i == j) {
                continue;
            }
            L.clear();
            R.clear();
            for (k=1;k<=n;k++) {
                if (i == k) {
                    L.push_back(i);
                    continue;
                }
                if (j == k) {
                    R.push_back(j);
                    continue;
                }
                if (det(v[i].x, v[i].y, v[j].x, v[j].y, v[k].x, v[k].y) < 0) {
                    L.push_back(k);
                } else {
                    R.push_back(k);
                }
            }
            if (L.size() < 3)
                continue;
            if (R.size() < 3)
                continue;
            stanga = poly(L, D);
            if (stanga == 0)
                continue;
            dreapta = poly(R, E);
            if (dreapta == 0)
                continue;

            //for (deque<int>::iterator it = D.begin(); it != D.end(); it++  )
            //    cout<<*it<<" ";
            //cout<<"\n";

            ariaStanga = aria(D);
            ariaDreapta = aria(E);

            if (modul( ariaStanga - ariaDreapta ) < minim) {
                minim = modul(ariaStanga - ariaDreapta);
                F.reset();
                for (int k = 0; k<L.size();k++) {
                    F[ v[ L[k] ].poz ] = 1;
                }
                if (F[1] == 0)
                    F = ~F;
            } else {
                if ( modul( ariaStanga - ariaDreapta ) == minim ) {
                    G.reset();
                    for (int k = 0; k<L.size();k++) {
                        G[ v[ L[k] ].poz ] = 1;
                    }
                    if (G[1] == 0)
                        G = ~G;
                    for (int k=1;k<=n;k++)
                        if (F[i] != G[i]) {
                            if (F[i] == 0) {
                                F = G;
                            }
                            break;
                        }
                }

            }
        }

    fout<<minim/2;
    if (minim % 2 == 0)
        fout<<".0\n";
    else
        fout<<".5\n";

    for (i=1;i<=n;i++)
        if (F[i] == 1)
            fout<<"I";
        else
            fout<<"V";

    return 0;
}