Pagini recente » Cod sursa (job #390186) | Cod sursa (job #2459805) | Cod sursa (job #3158463) | Cod sursa (job #655298) | Cod sursa (job #1861893)
#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 sol;
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) stk.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;
sol.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 ++ ) {
if( i == j )
continue;
lst1.clear(); lst2.clear();
for( int k = 0; k < n; k ++ ) {
if( k == i || k == j ) {
if( k == i )
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 );
if( arr1 != LLONG_MAX && arr2 != LLONG_MAX && abs( arr1 - arr2 ) < minim ) {
minim = abs( arr1 - arr2 );
for( tiii t : lst1 )
sol[get<2>(t)] = 'I';
for( tiii t : lst2 )
sol[get<2>(t)] = 'V';
if( sol[0] == 'V' )
for_each( sol.begin(), sol.end(), [](char x) { return ( ( x == 'I' ) ? 'V' : 'I' ); } );
}
else {
if( arr1 != LLONG_MAX && arr2 != LLONG_MAX && abs( arr1 - arr2 ) == minim ) {
string aux( sol.length(), 'a' );
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( sol > aux )
sol = aux;
}
}
}
}
out << setprecision( 1 ) << fixed << minim / 2.0 << endl << sol << endl;
return 0;
}