Cod sursa(job #863125)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 23 ianuarie 2013 14:57:35
Problema Gradina Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define INF 1e15
#define MAXN 255

struct Point {
    int x, y;
};

int N;
Point P[MAXN];
int FIRST;
int st[MAXN];
int head;
char distr1[MAXN], distr2[MAXN];
string minDistr;

long long crossProduct(const Point &A, const Point &B, const Point &C) {
    return (long long)(B.x - A.x) * (C.y - A.y) - (long long)(B.y - A.y) * (C.x - A.x);
}

bool cmp(const int &A, const int &B) {
    return crossProduct(P[FIRST], P[A], P[B]) > 0;
}

void convexHull(vector<int> &pts, vector<int> &R) {
    size_t first = 0;
    for(size_t i = 0; i < pts.size(); i++)
        if(P[pts[i]].y < P[pts[first]].y)
            first = i;

    swap(pts[first], pts[0]);
    FIRST = pts[0];
    sort(pts.begin(), pts.end(), cmp);

    st[0] = pts[0];
    st[1] = pts[1];
    head = 1;
    for(size_t i = 2; i < pts.size(); i++) {
        while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[pts[i]]) < 0) // > 1 ?
            head--;
        st[++head] = pts[i];
    }

    for(int i = 0; i <= head; i++)
        R.push_back(st[i]);
}

double ariePoligon(vector<int> &pts) {
    double ret = 0.0;
    for(size_t i = 1; i + 1 < pts.size(); i++)
        ret += crossProduct(P[pts[0]], P[pts[i]], P[pts[i + 1]]);
    return fabs(ret / 2.0);
}

string getDistr(vector<int> P[2]) {
    for(int i = 0; i < 2; i++)
        for(size_t j = 0; j < P[i].size(); j++) {
            if(i == 0) {
                distr1[P[i][j]] = 'I';
                distr2[P[i][j]] = 'V';
            }
            else {
                distr1[P[i][j]] = 'V';
                distr2[P[i][j]] = 'I';
            }
        }
    string v1(distr1);
    string v2(distr2);
    return min(v1, v2);
}

int main() {
	freopen("gradina.in", "r", stdin);
	freopen("gradina.out","w", stdout);

    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d %d", &P[i].x, &P[i].y);

    double minDiff = INF;
    for(int x = 0; x < N; x++)
        for(int y = 0; y < N; y++)
            if(x != y) {
                vector<int> sp[2];
                sp[0].push_back(x);
                sp[1].push_back(y);

                for(int i = 0; i < N; i++)
                    if(i != x && i != y) {
                        long long cp = crossProduct(P[x], P[y], P[i]);
                        int side = (cp > 0);
                        sp[side].push_back(i);
                    }

                vector<int> inf[2];
                convexHull(sp[0], inf[0]);
                if(sp[0].size() != inf[0].size())
                    continue;

                convexHull(sp[1], inf[1]);
                if(sp[1].size() != inf[1].size())
                    continue;

                double arie[2];
                arie[0] = ariePoligon(inf[0]);
                arie[1] = ariePoligon(inf[1]);

                double diff = fabs(arie[0] - arie[1]);
                if(diff < minDiff) {
                    minDiff = diff;
                    minDistr = getDistr(inf);
                }
                else if(diff == minDiff) {
                    string s = getDistr(inf);
                    if(s < minDistr)
                        minDistr = s;
                }
            }

    printf("%.1f\n", minDiff);
    printf("%s\n", minDistr.c_str());

	return 0;
}