Cod sursa(job #1250327)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 27 octombrie 2014 23:53:57
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <cstring>

#define x first
#define y second
#define NMAX 257
#define LL long long

using namespace std;

string Ans;
pair < int, int > a[NMAX];
vector < int > Sol1, Sol2, Sol3, Sol4;
char s[2][NMAX];
int Ind[NMAX];
LL Min = (1 << 30);
int Viz[NMAX];

inline bool Cmp(int Ind1, int Ind2){
    if(a[Ind1].x == a[Ind2].x)
        return a[Ind1].y < a[Ind2].y;
    return a[Ind1].x < a[Ind2].x;;
}

inline LL cp(pair < int, int> A, pair < int, int > B , pair < int, int > C){
    return 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
}

inline LL solve(vector < int > v) {
    LL area = 0;
    for(int i = 1; i + 1 < v.size(); ++i)
        area += cp(a[v[0]], a[v[i]], a[v[i + 1]]);
    return abs(area);
}

inline int cmp(pair < int, int> p1, pair < int, int> p2){
    return cp(a[1], p1, p2) < 0;
}

void Infasuratoare(vector < int > &v, vector < int > &SOL){
    if(v.size() < 3)
        return ;
    SOL.clear();
    SOL.push_back(v[0]);
    SOL.push_back(v[1]);
    memset(Viz, 0, sizeof(Viz));
    Viz[v[1]] = 1;
    for(int i = 2 ; i < v.size() ; ++ i) {
        if(Viz[v[i]])
            continue;
        while(SOL.size() >= 2 && cp(a[SOL[SOL.size() - 2]], a[SOL[SOL.size() - 1]], a[v[i]]) < 0) {
            Viz[SOL[SOL.size() - 1]] = 0;
            SOL.pop_back();
        }
        Viz[v[i]] = 1;
        SOL.push_back(v[i]);
    }
    for(int i = v.size() - 1 ; i >= 0 ; -- i) {
        if(Viz[v[i]])
            continue;
        while(SOL.size() >= 2 && cp(a[SOL[SOL.size() - 2]], a[SOL[SOL.size() - 1]], a[v[i]]) < 0) {
            Viz[SOL[SOL.size() - 1]] = 0;
            SOL.pop_back();
        }
        Viz[v[i]] = 1;
        SOL.push_back(v[i]);
    }
    SOL.pop_back();
}

inline string make_solution(vector < int > Sol3, vector < int > Sol4) {
    for(int j = 0 ; j < Sol3.size() ; ++j){
        s[0][Sol3[j]] = 'I';
        s[1][Sol3[j]] = 'V';
    }
    for(int j = 0 ; j < Sol4.size() ; ++j){
        s[0][Sol4[j]] = 'V';
        s[1][Sol4[j]] = 'I';
    }
    string s1(s[0] + 1);
    string s2(s[1] + 1);
    return min(s1, s2);
}

int main(){
    int n;
    freopen("gradina.in", "r", stdin);
    ofstream out("gradina.out");
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int A, B;
        scanf("%d %d", &A, &B);
        a[i] = make_pair(A, B);
        Ind[i] = i;
    }
    sort(Ind + 1, Ind + n + 1, Cmp);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){
            Sol1.clear();
            Sol2.clear();
            for(int k = 1; k <= n; ++k){
                if(k == i)
                    Sol1.push_back(Ind[k]);
                else
                    if(k == j)
                        Sol2.push_back(Ind[k]);
                    else{
                        if(cp(a[Ind[i]], a[Ind[j]], a[Ind[k]]) > 0)
                            Sol1.push_back(Ind[k]);
                        else
                            Sol2.push_back(Ind[k]);
                    }
            }
            Sol3.clear();
            Sol4.clear();
            Infasuratoare(Sol1, Sol3);
            Infasuratoare(Sol2, Sol4);
            if(Sol1.size() == Sol3.size() && Sol2.size() == Sol4.size()){
                LL Area = fabs(solve(Sol3) - solve(Sol4));
                ///out <<  i << ' ' <<  j << '\n';
                if(Area < Min){
                    Min = Area;
                    Ans = make_solution(Sol3, Sol4);
                }
                if(Area == Min)
                    Ans = min(Ans, make_solution(Sol3, Sol4));
            }
        }
    out << fixed << setprecision(1) << Min * 0.5 << '\n' << Ans << '\n';
    return 0;
}