Cod sursa(job #2958229)

Utilizator vladburacBurac Vlad vladburac Data 25 decembrie 2022 09:45:05
Problema Gradina Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX = 255;
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 = 1LL * a.x * b.y + 1LL * b.x * c.y + 1LL * c.x * a.y - 1LL * a.y * b.x - 1LL * b.y * c.x - 1LL * 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;
}
signed 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;
}