Pagini recente » Cod sursa (job #1813529) | Cod sursa (job #3203231) | Cod sursa (job #690460) | Cod sursa (job #1979449) | Cod sursa (job #942192)
Cod sursa(job #942192)
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std ;
#define maxn ( 1 << 8 )
#define inf 1000000
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 ;
}