Cod sursa(job #1862279)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 ianuarie 2017 18:30:17
Problema Gradina Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "gradina.in" , ios::in  );
fstream out( "gradina.out", ios::out );

typedef tuple<int, int, int> tiii;

vector<tiii> pts, lst1, lst2; string ans, aux;

long long ccw( tiii p1, tiii p2, tiii p3 ) {
    return ( get<0>(p2) - get<0>(p1) ) * 1LL * ( get<1>(p3) - get<1>(p1) ) -
           ( get<0>(p3) - get<0>(p1) ) * 1LL * ( get<1>(p2) - get<1>(p1) );
}

long long slv( vector<tiii> lst ) {
    vector<int> mrk( lst.size() ), stk( 1, 0 );
    
    for( int i = 1, aux = (int) stk.size(); i < lst.size(); i ++ ) {
        if( mrk[i] == 1 )
            continue;
        
        while( stk.size() > aux && ccw( lst[stk[stk.size() - 2]], lst[stk[stk.size() - 1]], lst[i] ) > 0 ) {
            mrk[stk.back()] = 0;
            stk.pop_back();
        }
        
        mrk[i] = 1;
        stk.push_back( i );
    }
    
    for( int i = (int) lst.size() - 1, aux = (int) stk.size(); i > -1; i -- ) {
        if( mrk[i] == 1 )
            continue;
        
        while( stk.size() > aux && ccw( lst[stk[stk.size() - 2]], lst[stk[stk.size() - 1]], lst[i] ) > 0 ) {
            mrk[stk.back()] = 0;
            stk.pop_back();
        }
        
        mrk[i] = 1;
        stk.push_back( i );
    }
    
    if( count( mrk.begin(), mrk.end(), 1 ) != mrk.size() || mrk.size() < 3 )
        return LLONG_MAX;
    else {
        long long arr = 0;
        for( int i = 1; i < stk.size(); i ++ )
            arr += ccw( lst[stk[i - 1]], lst[stk[i]], make_tuple( 0, 0, 0 ) );
        
        return abs( arr );
    }
}

int main( void ) {
    ios::sync_with_stdio( false );
    
    int n;
    in >> n;
    
    ans.resize( n ), aux.resize( n );
    for( int i = 0; i < n; i ++ ) {
        int x, y;
        in >> x >> y;
        
        pts.push_back( make_tuple( x, y, i ) );
    }
    
    sort( pts.begin(), pts.end() );
    
    long long minim = LLONG_MAX;
    for( int i = 0; i < n; i ++ ) {
        for( int j = 0; j < n; j ++ ) {
            int ii = min( i, j ), jj = max( i, j );
           
            if( i == j )
                continue;
            
            lst1.clear(); lst2.clear();
            for( int k = 0; k < n; k ++ ) {
                if( k == i || k == j ) {
                    if( k == ii )
                        lst1.push_back( pts[k] );
                    else
                        lst2.push_back( pts[k] );
                }
                else {
                    if( ccw( pts[i], pts[j], pts[k] ) > 0 )
                        lst1.push_back( pts[k] );
                    else
                        lst2.push_back( pts[k] );
                }
            }
            
            long long arr1 = slv( lst1 ), arr2 = slv( lst2 );
            
            for( tiii t : lst1 )
                aux[get<2>(t)] = 'I';
            for( tiii t : lst2 )
                aux[get<2>(t)] = 'V';
            
            if( aux[0] == 'V' )
                for_each( aux.begin(), aux.end(), [](char x){
                    return ( x == 'I' ) ? 'V' : 'I'; } );
        
            if( arr1 != LLONG_MAX && arr2 != LLONG_MAX ) {
                if( minim > abs( arr1 - arr2 ) ) {
                    minim = abs( arr1 - arr2 );
                    ans = aux;
                }
                else {
                    if( minim == abs( arr1 - arr2 ) )
                        ans = min( ans, aux );
                }
            }
        }
    }
    
    out << setprecision(1) << fixed << minim / 2.0 << endl << ans << endl;
    return 0;
}