Cod sursa(job #2695049)

Utilizator stefantagaTaga Stefan stefantaga Data 11 ianuarie 2021 17:21:25
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
struct wow
{
    int x,y;
} t1[300],t2[300],a[300];
int n,aux,vft1,vft2,st[300];
char S[300],ch[300];
double Min;
bool marker[300];
bool cmp(wow a,wow b)
{
    if(a.x>b.x)return false;
    if(a.x==b.x && a.y>b.y)return false;
    return true;
}
int det(wow a,wow b,wow c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double functie(wow p[],int m)
{
    double sol=0;
    for(int i=1; i<=m; i++)
    {
        marker[i]=false;
    }
    st[1]=1;
    st[2]=2;
    marker[2]=true;
    int vf=2;
    int poz=2;
    int pas=1;
    while(marker[1]==false)
    {
        while(marker[poz]==true)
        {
            poz+=pas;
            if(poz==m)pas=-1;
        }
        while(vf>=2 && det(p[st[vf-1]],p[st[vf]],p[poz])<0)
        {
            marker[st[vf]]=false;
            vf--;
        }
        vf++;
        st[vf]=poz;
        marker[poz]=true;
    }
    for(int i=1; i<vf; i++)
    {
        sol=sol+det(p[0],p[st[i]],p[st[i+1]]);
    }
    sol=sol/2;
    if(vf!=m+1)
    {
        aux=0;
    }
    return sol;
}
void Solve()
{
    Min=1000000000;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            vft1=0;
            vft2=0;
            if(i==1||det(a[1],a[i],a[j])<0)
            {
                for(int k=1; k<=n; k++)
                {
                    if(k==i || k==j || det(a[k],a[i],a[j])<0)
                    {
                        ch[k]='I';
                        vft1++;
                        t1[vft1]=a[k];
                    }
                    else
                    {
                        ch[k]='V';
                        vft2++;
                        t2[vft2]=a[k];
                    }
                }
            }
            else
            {
                for(int k=1; k<=n; k++)
                {
                    if(k==i || k==j || det(a[k],a[i],a[j])<0)
                    {
                        ch[k]='V';
                        vft2++;
                        t2[vft2]=a[k];
                    }
                    else
                    {
                        ch[k]='I';
                        vft1++;
                        t1[vft1]=a[k];
                    }
                }
            }
            if(vft1<3 || vft2<3)continue;
            sort(t1+1,t1+vft1+1,cmp);
            sort(t2+1,t2+vft2+1,cmp);
            aux=1;
            double dif=abs(functie(t1,vft1)-functie(t2,vft2));
            if(aux==0)continue;
            if(dif<Min)
            {
                Min=dif;
                for(int k=1; k<=n; k++)S[k]=ch[k];
            }
        }
    }
    g<<setprecision(1)<<fixed;
    g<<Min<<'\n';
    for(int i=1; i<=n; i++)
    {
        g<<S[i];
    }
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>a[i].x>>a[i].y;
    }
    Solve();
    return 0;
}