Cod sursa(job #1669840)

Utilizator robx12lnLinca Robert robx12ln Data 31 martie 2016 09:45:02
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.04 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<deque>
#include<bitset>
#define x first.first
#define y first.second
#define poz second
#define DIM 255
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int n;
pair< pair<int,int>, int > p[DIM];
bitset<DIM> F, SOL;
long long sol;
vector<int> L, R;
deque<int> D, S;
long long det( int X1, int Y1, int X2, int Y2, int X3, int Y3 ){
    return 1LL * ( X2 - X1 ) * ( Y3 - Y1 ) - 1LL * ( X3 - X1 ) * ( Y2 - Y1 );
}
int poligon( vector<int> v, deque<int> &d ){
    d.clear();
    d.push_back( v[0] );
    for( int i = 1; i < v.size() - 1; i++ ){
        if( det( p[v[0]].x, p[v[0]].y, p[v.back()].x, p[v.back()].y, p[v[i]].x, p[v[i]].y ) > 0 ){
            d.push_back( v[i] );
        }else{
            d.push_front( v[i] );
        }
    }
    d.push_back( v.back() );
    D.push_back( d.front() );
    for( int i = 0; i < d.size() - 2; i++ ){
        if( det( p[ d[i] ].x, p[ d[i] ].y, p[ d[i + 1] ].x, p[ d[i + 1] ].y, p[ d[i + 2] ].x, p[ d[i + 2] ].y ) > 0 ){
            return 0;
        }
    }
    return 1;
}
long long aria( deque<int> d ){
    long long a = 0;
    for( int i = 0; i < d.size() - 1; i++ ){
        a += det( 0, 0, p[i].x, p[i].y, p[i + 1].x, p[i + 1].y );
    }
    if( a < 0 ){
        a = 0 - a;
    }
    return a;
}
long long modul( long long X ){
    if( X < 0 ){
        X = 0 - X;
    }
    return X;
}
int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        fin >> p[i].x >> p[i].y;
        p[i].poz = i;
    }
    sol = 100000000000000LL;
    sort( p + 1, p + n + 1 );
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= n; j++ ){
            if( i == j )
                continue;
            L.clear();
            R.clear();
            for( int k = 1; k <= n; k++ ){
                if( i == k ){
                    L.push_back(i);
                }
                if( j == k ){
                    R.push_back(j);
                }
                if( det( p[i].x, p[i].y, p[j].x, p[j].y, p[k].x, p[k].y ) < 0 ){
                    L.push_back(k);
                }else{
                    R.push_back(k);
                }
            }
            if( L.size() < 3 ){
                continue;
            }
            if( R.size() < 3 ){
                continue;
            }
            int st = poligon( L, S );
            if( st == 0 ){
                continue;
            }
            int dr = poligon( R, D );
            if( dr == 0 ){
                continue;
            }
            long long ast = aria(S);
            long long adr = aria(D);
            if( modul( ast - adr ) < sol ){
                sol = modul( ast - adr );
                SOL.reset();
                // 1 pt I
                // 0 pt V
                for( int k = 0; k < L.size(); k++ ){
                    SOL[ p[ L[k] ].poz ] = 1;
                }
                if( SOL[1] == 0 ){
                    SOL = ~SOL;
                }
            }else{
                if( modul( ast - adr ) == sol ){
                    F.reset();
                    // 1 pt I
                    // 0 pt V
                    for( int k = 0; k < L.size(); k++ ){
                        F[ p[ L[k] ].poz ] = 1;
                    }
                    if( F[1] == 0 ){
                        F = ~F;
                    }
                    for( int k = 1; k <= n; k++ ){
                        if( F[k] != SOL[k] ){
                            if( F[k] == 1 ){
                                SOL = F;
                            }
                            break;
                        }
                    }
                }
            }
        }
    }
    fout << sol / 2;
    if( sol % 2 == 0 ){
        fout << ".0\n";
    }else{
        fout << ".5\n";
    }
    for( int i = 1; i <= n; i++ ){
        if( SOL[i] == 1 ){
            fout << "I";
        }else{
            fout << "V";
        }
    }
    return 0;
}