Pagini recente » Cod sursa (job #2149347) | Cod sursa (job #2842687) | Cod sursa (job #287790) | Cod sursa (job #1937196) | Cod sursa (job #1669840)
#include<fstream>
#include<algorithm>
#include<vector>
#include<deque>
#include<bitset>
#define x first.first
#define y first.second
#define poz second
#define DIM 255
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
int n;
pair< pair<int,int>, int > p[DIM];
bitset<DIM> F, SOL;
long long sol;
vector<int> L, R;
deque<int> D, S;
long long det( int X1, int Y1, int X2, int Y2, int X3, int Y3 ){
return 1LL * ( X2 - X1 ) * ( Y3 - Y1 ) - 1LL * ( X3 - X1 ) * ( Y2 - Y1 );
}
int poligon( vector<int> v, deque<int> &d ){
d.clear();
d.push_back( v[0] );
for( int i = 1; i < v.size() - 1; i++ ){
if( det( p[v[0]].x, p[v[0]].y, p[v.back()].x, p[v.back()].y, p[v[i]].x, p[v[i]].y ) > 0 ){
d.push_back( v[i] );
}else{
d.push_front( v[i] );
}
}
d.push_back( v.back() );
D.push_back( d.front() );
for( int i = 0; i < d.size() - 2; i++ ){
if( det( p[ d[i] ].x, p[ d[i] ].y, p[ d[i + 1] ].x, p[ d[i + 1] ].y, p[ d[i + 2] ].x, p[ d[i + 2] ].y ) > 0 ){
return 0;
}
}
return 1;
}
long long aria( deque<int> d ){
long long a = 0;
for( int i = 0; i < d.size() - 1; i++ ){
a += det( 0, 0, p[i].x, p[i].y, p[i + 1].x, p[i + 1].y );
}
if( a < 0 ){
a = 0 - a;
}
return a;
}
long long modul( long long X ){
if( X < 0 ){
X = 0 - X;
}
return X;
}
int main(){
fin >> n;
for( int i = 1; i <= n; i++ ){
fin >> p[i].x >> p[i].y;
p[i].poz = i;
}
sol = 100000000000000LL;
sort( p + 1, p + n + 1 );
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= n; j++ ){
if( i == j )
continue;
L.clear();
R.clear();
for( int k = 1; k <= n; k++ ){
if( i == k ){
L.push_back(i);
}
if( j == k ){
R.push_back(j);
}
if( det( p[i].x, p[i].y, p[j].x, p[j].y, p[k].x, p[k].y ) < 0 ){
L.push_back(k);
}else{
R.push_back(k);
}
}
if( L.size() < 3 ){
continue;
}
if( R.size() < 3 ){
continue;
}
int st = poligon( L, S );
if( st == 0 ){
continue;
}
int dr = poligon( R, D );
if( dr == 0 ){
continue;
}
long long ast = aria(S);
long long adr = aria(D);
if( modul( ast - adr ) < sol ){
sol = modul( ast - adr );
SOL.reset();
// 1 pt I
// 0 pt V
for( int k = 0; k < L.size(); k++ ){
SOL[ p[ L[k] ].poz ] = 1;
}
if( SOL[1] == 0 ){
SOL = ~SOL;
}
}else{
if( modul( ast - adr ) == sol ){
F.reset();
// 1 pt I
// 0 pt V
for( int k = 0; k < L.size(); k++ ){
F[ p[ L[k] ].poz ] = 1;
}
if( F[1] == 0 ){
F = ~F;
}
for( int k = 1; k <= n; k++ ){
if( F[k] != SOL[k] ){
if( F[k] == 1 ){
SOL = F;
}
break;
}
}
}
}
}
}
fout << sol / 2;
if( sol % 2 == 0 ){
fout << ".0\n";
}else{
fout << ".5\n";
}
for( int i = 1; i <= n; i++ ){
if( SOL[i] == 1 ){
fout << "I";
}else{
fout << "V";
}
}
return 0;
}