Cod sursa(job #961155)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 18:00:44
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std ;
 
#define maxn ( 1 << 8 )
#define inf ( 1 << 30 )
 
struct punct
{
    int x, y, unde ;
};
 
punct a[maxn], b[maxn], c[maxn] ;
 
int n, lenb, lenc ;
 
int stiva[maxn], sel[maxn] ;
 
int sol ;
 
string aux, rez ;
 
bool cmp( punct A, punct B )
{
    if( A.x != B.x )
        return A.x < B.x ;
    return A.y < B.y ;
}
 
void citire()
{
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);
 
    cin >> n ;
 
    for(int i = 1; i <= n; ++i )
    {
        cin >> a[i].x >> a[i].y ;
        a[i].unde = i ;
    }
}
 
int verifica( punct A, punct B, punct C )
{
    return A.x * ( B.y - C.y ) + B.x * ( C.y - A.y ) + C.x * ( A.y - B.y ) ;
}
 
int arie_infasuratoare( punct v[], int n )
{
    if( n < 3 )
        return 0 ;
 
    stiva[0] = 1 ;
    stiva[1] = 2 ;
 
    memset( sel, 0, sizeof(sel) ) ;
 
    int ind = 2, top = 1, pas = 1 ;
 
    sel[2] = 1 ;
 
    while( sel[1] == 0 )
    {
        if( ind == n )
            pas = -1 ;
 
        while( sel[ind] == 1 )
            ind += pas ;
 
        while( top && verifica( v[ stiva[ top - 1 ] ], v[ stiva[top] ], v[ind] ) > 0 )
            sel[ stiva[ top-- ] ] = 0 ;
 
        stiva[ ++top ] = ind ;
        sel[ind] = 1 ;
    }
 
    int arie = 0 ;
 
    if( top != n )
        return 0 ;
 
    for(int i = 1; i <= top; ++i )
        arie += v[ stiva[ i - 1 ] ].x * v[ stiva[i] ].y - v[ stiva[i] ].x * v[ stiva[ i - 1 ] ].y ;
 
    return max( arie, -arie ) ;
}
 
void rezolvare()
{
    sort( a + 1, a + n + 1, cmp ) ;
 
    sol = inf ;
 
    aux.resize( n ) ;
 
    for(int i = 1; i <= n; ++i )
    {
        for(int j = 1; j <= n; ++j )
        {
            if( i != j )
            {
                lenb = lenc = 0 ;
 
                for(int k = 1; k <= n; ++k )
                {
                    if( k != i && k != j )
                    {
                        if( verifica( a[i], a[j], a[k] ) > 0 )
                            b[ ++lenb ] = a[k] ;
                        else
                            c[ ++lenc ] = a[k] ;
                    }
                    else
                    {
                        if( k == i )
                            b[ ++lenb ] = a[k] ;
                        else
                            c[ ++lenc ] = a[k] ;
                    }
                }
 
                int X = arie_infasuratoare( b, lenb ) ;
                int Y = arie_infasuratoare( c, lenc ) ;
 
                if( X && Y )
                {
                    int act = max( X - Y, Y - X ) ;
 
                    if( act <= sol )
                    {
                        for(int k = 1; k <= lenb; ++k )
                            aux[ b[k].unde - 1 ] = 'I' ;
 
                        for(int k = 1; k <= lenc; ++k )
                            aux[ c[k].unde - 1 ] = 'V' ;
 
                        if( act == sol )
                            rez = min( rez, aux ) ;
                        else
                            rez = aux ;
 
                        sol = act ;
                    }
                }
            }
        }
    }
}
 
void afisare()
{
    cout << setprecision(1) << fixed ;
 
    cout << (double) sol / 2.0 << "\n" ;
 
    cout << rez ;
}
 
int main()
{
    citire() ;
 
    rezolvare() ;
 
    afisare() ;
 
    return 0 ;
}