Cod sursa(job #3248169)

Utilizator sebigabiSebastian Itu sebigabi Data 10 octombrie 2024 22:09:53
Problema Gradina Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <string>
#define pdd pair<double, double>
using namespace std;

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

const int NMAX = 250;
int n;
pair<pdd, int> v[NMAX];

bool cmp(const pair<pdd, int>& a, const pair<pdd, int>& b)
{
    if(a.first.first < b.first.first)
    {
        return 1;
    }
    if(a.first.first == b.first.first)
    {
        return a.first.second < b.first.second;
    }
    if(a.first.first > b.first.first)
    {
        return 0;
    }
    return 0;
}

double arie(pdd A, pdd B, pdd C)
{
    return ((A.first * B.second + B.first * C.second + C.first * A.second)
           -(C.first * B.second + A.first * C.second + B.first * A.second)) / 2;
}

double infasoara(pdd pct[], int len)
{
    int stiva[NMAX];
    bool tip[NMAX];
    for(int i=1; i<len-1; i++)
    {
        if(arie(pct[0], pct[len-1], pct[i]) < 0)
        {
            tip[i] = 0;
        }
        else
        {
            tip[i] = 1;
        }
    }

    int vf = 0;
    stiva[vf] = 0;

    for(int i=1; i<len; i++)
    {
        if(i==len-1 || tip[i] == 0)
        {
            while(vf > 0 && arie(pct[stiva[vf-1]], pct[stiva[vf]], pct[i]) < 0)
            {
                vf--;
                return -1; //e concav
            }
            vf++;
            stiva[vf] = i;
        }
    }

    int last_size = vf;

    for(int i=len-2; i>=0; i--)
    {
        if(i == 0 || tip[i] == 1)
        {
            while(vf > last_size && arie(pct[stiva[vf-1]], pct[stiva[vf]], pct[i]) < 0)
            {
                vf--;
                return -1; //e concav
            }
            vf++;
            stiva[vf] = i;
        }
    }

    if(vf < 3)//nu exista poligon cu mai putin de 3 varfuri
    {
        return -1;
    }

    double area = 0;
    for(int i=1; i<vf-1; i++)
    {
        area += abs(arie(pct[0], pct[stiva[i]], pct[stiva[i+1]]));
    }

    return abs(area);
}

void solve()
{
    double ariemin = 100000000;
    string solmin(NMAX, 'Z');

    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            bool tip[NMAX];
            string temp(NMAX, 'Z');
            for(int k=0; k<n; k++)
            {
                tip[k] = (arie(v[i].first, v[j].first, v[k].first) >= 0);
                if(tip[k] == 0)
                {
                    temp[v[k].second] = 'I';
                }
                else
                {
                    temp[v[k].second] = 'V';
                }
            }

            tip[i] = 0; temp[v[i].second] = 'I';
            tip[j] = 1; temp[v[j].second] = 'V';

            if(v[j].second < v[i].second)
            {
                tip[i] = 1; temp[v[i].second] = 'V';
                tip[j] = 0; temp[v[j].second] = 'I';
            }

            pdd v1[NMAX], v2[NMAX];
            int n1=0, n2=0;
            for(int k=0; k<n; k++)
            {
                if(tip[k] == 0)
                {
                    v1[n1++] = v[k].first;
                }
                else
                {
                    v2[n2++] = v[k].first;
                }
            }


            if(n1 >= 3 && n2 >= 3) //nu exista poligon cu mai putin de 3 varfuri
            {
                double area1 = infasoara(v1, n1);
                double area2 = infasoara(v2, n2);

                if(area1 != -1 && area2 != -1)
                {
                    double area = abs(area1-area2);
                    if(area < ariemin)
                    {
                        ariemin = area;
                        solmin = temp;
                    }
                    if(area == ariemin)
                    {
                        if(temp < solmin)
                        {
                            solmin = temp;
                        }
                    }
                }
            }
        }
    }

    out<<fixed<<setprecision(1)<<ariemin<<"\n";
    for(int i=0; i<n; i++)
    {
        out<<solmin[i];
    }
}

int main()
{
    in>>n;

    for(int i=0; i<n; i++)
    {
        double x,y;
        in>>x>>y;
        v[i] = {{x,y}, i};
    }
    sort(v, v+n, cmp);

    solve();
    return 0;
}