Pagini recente » Cod sursa (job #995983) | Cod sursa (job #511243) | Cod sursa (job #2639745) | Cod sursa (job #2363090) | Cod sursa (job #1862279)
#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;
}