Pagini recente » Cod sursa (job #1860345) | Cod sursa (job #2193700) | Cod sursa (job #627313) | Cod sursa (job #3240530) | Cod sursa (job #2958227)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 250;
const int INF = 5e7 + 1;
const int EPS = 1e-7;
ifstream fin( "gradina.in" );
ofstream fout( "gradina.out" );
struct Point{
int x;
int y;
};
Point v[NMAX];
Point v1[NMAX], v2[NMAX];
int k1, k2;
int temp_ans[NMAX];
int ans[NMAX];
inline long long orientation( Point a, Point b, Point c ) {
long long compute;
compute = 1LL * ( b.y - a.y ) * ( c.x - b.x ) - 1LL * ( b.x - a.x ) * ( c.y - b.y );
return compute;
}
inline bool isTrigo( Point a, Point b, Point c ) {
long long x = orientation( a, b, c );
if( x < 0 )
return true;
return false;
}
Point elem;
bool cmp( Point a, Point b ) {
return isTrigo( elem, a, b );
}
bool isConvex( Point *v, int n, int pos ) {
int i, minx, miny, ind;
minx = miny = INF;
for( i = 0; i < n; i++ ) {
if( v[i].y < miny ) {
ind = i;
miny = v[i].y;
minx = v[i].x;
}
else if( v[i].y == miny && v[i].x < minx ) {
ind = i;
minx = v[i].x;
}
}
swap( v[0], v[ind] );
if( pos == 0 )
elem = v1[0];
else
elem = v2[0];
sort( v + 1, v + n, cmp );
i = 0;
while( i < n - 2 && isTrigo( v[i], v[i+1], v[i+2] ) )
i++;
if( i == n - 2 && isTrigo( v[n-2], v[n-1], v[0] ) )
return true;
return false;
}
inline long double getArea( Point a, Point b, Point c ) {
long double arie;
arie = a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
arie /= 2;
return arie;
}
inline long double area( Point *v, int n ) {
long double a = 0;
int i;
for( i = 1; i < n - 1; i++ )
a += getArea( v[0], v[i], v[i+1] );
return a;
}
int main() {
int n, i, j, k;
long double a1, a2, arie, mini;
fin >> n;
for( i = 0; i < n; i++ ) {
fin >> v[i].x >> v[i].y;
}
mini = 1000000000.0;
for( i = 0; i < n; i++ ) {
for( j = 0; j < n; j++ ) {
if( i != j ) {
k1 = k2 = 0;
v1[k1++] = v[i];
v1[k1++] = v[j];
temp_ans[i] = temp_ans[j] = 1;
for( k = 0; k < n; k++ ) {
if( k != i && k != j ) {
if( isTrigo( v[i], v[j], v[k] ) )
v1[k1++] = v[k], temp_ans[k] = 1;
else
v2[k2++] = v[k], temp_ans[k] = 2;
}
}
if( isConvex( v1, k1, 0 ) && isConvex( v2, k2, 1 ) ) {
a1 = area( v1, k1 );
a2 = area( v2, k2 );
arie = abs( a1 - a2 );
if( arie < mini || abs( arie - mini ) < EPS ) {
mini = arie;
for( k = 0; k < n; k++ )
ans[k] = temp_ans[k];
}
}
}
}
}
fout << setprecision( 1 ) << fixed;
fout << mini << "\n";
for( i = 0; i < n; i++ ) {
if( ans[i] == ans[0] )
fout << "I";
else
fout << "V";
}
return 0;
}