Cod sursa(job #2711247)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 23 februarie 2021 20:09:37
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <bits/stdc++.h>

#define NMAX 255
#define EPS 0.0000001
using namespace std;

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

struct chestie
{
    long long x, y;
    int care;
} vec[NMAX], v1[NMAX], v2[NMAX], aux, st[NMAX];

int nr1, nr2, tip[NMAX], n;
double minn = LLONG_MAX / 2;
string sol;

double det(chestie x1, chestie x2, chestie x3)
{
    return ((x1.x * x2.y) + (x1.y * x3.x) + (x2.x * x3.y) - (x3.x * x2.y) - (x1.y * x2.x) - (x1.x * x3.y));
}

inline bool cmp1(chestie a, chestie b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

inline bool cmp2(chestie a, chestie b)
{
    return (det(aux, a, b) > 0.0);
}

bool checkPolig(chestie v[NMAX], int nr)
{
    aux = v[1];
    sort(v + 2, v + nr + 1, cmp2);
    for(int i = 3; i <= nr; ++i)
        if(det(v[i - 2], v[i - 1], v[i]) <= 0.0)
            return 0;
    return 1;
}

double ariaTr(chestie a, chestie b, chestie c)
{
    a.x -= c.x;
    b.x -= c.x;
    a.y -= c.y;
    b.y -= c.y;
    return (double(a.x * b.y - b.x * a.y) / 2.0);
}

double getAria(chestie v[NMAX], int nr)
{
    v[nr + 1] = v[1];
    double rez = 0;
    for(int i = 2; i <= nr; ++i)
        rez += ariaTr(v[1], v[i], v[i + 1]);
    return rez;
}

string getSol()
{
    for(int i = 1; i <= nr1; ++i)
        tip[v1[i].care] = 1;
    for(int i = 1; i <= nr2; ++i)
        tip[v2[i].care] = 2;
    string rez = "";
    int val = tip[1];
    for(int i = 1; i <= n; ++i)
        if(tip[i] == val)
            rez += "I";
        else rez += "V";
    return rez;
}

int main()
{
    fin >> n;

    for(int i = 1; i <= n; ++i)
    {
        fin >> vec[i].x >> vec[i].y;
        vec[i].care = i;
    }

    sort(vec + 1, vec + n + 1, cmp1);
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
        {
            nr1 = nr2 = 0;
            for(int k = 1; k <= n; ++k)
            {
                double val = det(vec[i], vec[j], vec[k]);
                if(val < 0.0)
                    v1[++nr1] = vec[k];
                else v2[++nr2] = vec[k];
            }
            if(nr1 >= 3 && nr2 >= 3 && checkPolig(v1, nr1) && checkPolig(v2, nr2))
            {
                double aria = abs(getAria(v1, nr1) - getAria(v2, nr2));
                if(aria < minn)
                    minn = aria, sol = getSol();
                else if(fabs(aria - minn) < EPS)
                    sol = min(sol, getSol());
            }
        }

    fout << fixed << setprecision(1) << minn << '\n' << sol << '\n';
    return 0;
}