Cod sursa(job #1724320)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 2 iulie 2016 20:55:41
Problema Gradina Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

const int N_MAX = 256;
const int64_t INF = 0x3f3f3f3f3f3f3f3f;

struct Point {
  int x, y, id;
  bool operator <(const Point &o) const { return (x == o.x ? y < o.y : x < o.x); }
};

int N;
Point P[N_MAX];
bool preSol[N_MAX];
string Sol, bestSol;

int64_t Det(const Point &A, const Point &B, const Point &C) {
  return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}

int64_t getArea(const vector<Point> &P) {
  int64_t Area = 0;
  for(int i = 1; i < P.size(); i++) Area += llabs(Det(P[0], P[i - 1], P[i]));
  return Area;
}

vector<Point> getConvex(const vector<Point> &P) {
  vector<Point> H;
  int Stack[N_MAX], Top;
  
  Stack[0] = 0;
  Stack[1] = 1;
  Top = 1;
  for(int i = 2; i < P.size(); i++) {
    while(Top > 0 && Det(P[Stack[Top - 1]], P[Stack[Top]], P[i]) < 0) Top--;
    Stack[++Top] = i;
  } 
  for(int i = 0; i < Top; i++) H.push_back(P[Stack[i]]);
  
  Stack[0] = P.size() - 1;
  Stack[1] = P.size() - 2;
  Top = 1;
  for(int i = P.size() - 3; i >= 0; i--) {
    while(Top > 0 && Det(P[Stack[Top - 1]], P[Stack[Top]], P[i]) < 0) Top--;
    Stack[++Top] = i;
  }
  for(int i = 0; i < Top; i++) H.push_back(P[Stack[i]]);
  
  return H;
}

int64_t getDifference(int fixedFirst, int fixedSecond) {
  vector<Point> leftSide, rightSide, leftConvex, rightConvex;
  for(int i = 1; i <= N; i++) {
    if(i == fixedFirst || Det(P[fixedFirst], P[fixedSecond], P[i]) < 0) {
      leftSide.push_back(P[i]);
      preSol[i] = 0;
    } 
    else {
      rightSide.push_back(P[i]);
      preSol[i] = 1;
    }
  }
  leftConvex = getConvex(leftSide);
  if(leftSide.size() != leftConvex.size()) return INF;
  
  rightConvex = getConvex(rightSide);
  if(rightSide.size() != rightConvex.size()) return INF;
  
  for(int i = 1; i <= N; i++) 
    Sol[i] = (preSol[i] == preSol[0] ? 'I' : 'V');

  return llabs(getArea(leftConvex) - getArea(rightConvex));
}

int main() {
  freopen("gradina.in", "r", stdin);
  freopen("gradina.out", "w", stdout);
  
  scanf("%d", &N);
  for(int i = 1; i <= N; i++) {
    scanf("%d %d", &P[i].x, &P[i].y);
    P[i].id = i;
  }
  
  sort(P+1, P+N+1);

  int64_t minDiff = INF;
  int bestFirst, bestSecond;
  bestSol.assign(N + 1, 'V');
  Sol.assign(N + 1, 'V');
  
  for(int i = 1; i <= N; i++) {
    for(int j = i + 1; j <= N; j++) {
      if(i != j) {
        int64_t Diff = getDifference(i, j);
        if(minDiff > Diff || (minDiff == Diff && bestSol > Sol)) {
          minDiff = Diff;
          bestSol = Sol;
        }
      }
    }
  }
  
  for(int i = 1; i <= N; i++)
    Sol[P[i].id] = bestSol[i];
  
  printf("%.1f\n", 0.5 * minDiff);
  for(int i = 1; i <= N; i++) printf("%c", Sol[i]);
  printf("\n");
  
  return 0;
}