Cod sursa(job #1779142)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 14 octombrie 2016 20:44:03
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <iomanip>

using namespace std;

ifstream fin ("gradina.in"); ofstream fout ("gradina.out");

const int nmax = 250;
int n;
double arie;
string s;

struct pct{
    int x, y;
} centru, v[nmax + 1], a[nmax + 1], b[nmax + 1];

inline bool cmp (pct x, pct y) {
    return 1LL * (x.y - centru.y) * (y.x - centru.x) <
           1LL * (y.y - centru.y) * (x.x - centru.x);
}

inline int ccw (pct x, pct y, pct z) {
    long long ans = (1LL * x.x * y.y - 1LL * x.y * y.x +
                     1LL * y.x * z.y - 1LL * y.y * z.x +
                     1LL * z.x * x.y - 1LL * z.y * x.x);

    if (ans > 0) return 1;
    if (ans == 0) return 0;
    return -1;
}

double calc_arie (pct x[], int lg) {
    double ans = 0;
    for (int i = 0; i < lg - 1; ++ i) {
        ans += (1.0 * x[ i ].x * x[i + 1].y - 1.0 * x[i + 1].x * x[ i ].y);
    }
    ans += (1.0 * x[lg - 1].x * x[ 0 ].y - 1.0 * x[ 0 ].x * x[lg - 1].y);

    if (ans < 0) ans = -ans;
    return ans / 2;
}

bool infasuratoare (pct x[], int lg) {
    int ind = 0;
    for (int i = 1; i < lg; ++ i) {
        if (x[ ind ].x > x[ i ].x) {
            ind = i;
        } else if (x[ ind ].x == x[ i ].x && x[ ind ].y > x[ i ].y) {
            ind = i;
        }
    }

    swap(x[ 0 ], x[ ind ]);
    centru = x[ 0 ];
    sort(x + 1, x + lg, cmp);

    for (int i = 2; i < lg; ++ i) {
        if (ccw(x[i - 2], x[i - 1], x[ i ]) == -1) {
            return 0;
        }
    }

    return 1;
}

void solve (int x, int y) {
    string aux;
    aux.resize( n );

    int lga, lgb;
    lga = lgb = 0;

    for (int i = 0; i < n; ++ i) {
        int unde = ccw(v[ x ], v[ y ], v[ i ]);

        if (unde > 0 || i == x) {
            a[ lga ++ ] = v[ i ];
            aux[ i ] = 'I';
        } else {
            b[ lgb ++ ] = v[ i ];
            aux[ i ] = 'V';
        }
    }

    if (lga < 3 || lgb < 3) return ;
    if (infasuratoare(a, lga) == 0 || infasuratoare(b, lgb) == 0) return ;
    double dif = calc_arie(a, lga) - calc_arie(b, lgb);

    if (dif < 0) dif = -dif;

    if (aux[ 0 ] == 'V') {
        for (int i = 0; i < n; ++ i) {
            if (aux[ i ] == 'I') aux[ i ] = 'V';
            else aux[ i ] = 'I';
        }
    }

    if (dif < arie) {
        arie = dif;
        s = aux;
    } else if (dif == arie && aux < s) {
        s = aux;
    }
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++ i) {
        fin >> v[ i ].x >> v[ i ].y;
    }

    arie = INFINITY;
    for (int i = 0; i < n; ++ i) {
        for (int j = i + 1; j < n; ++ j) {
            solve(i, j);
        }
    }

    fout << setprecision( 1 ) << fixed;
    fout << arie << "\n" << s;

    fin.close();
    fout.close();
    return 0;
}