Cod sursa(job #3002878)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 15 martie 2023 12:04:18
Problema Gradina Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.22 kb
#include <bits/stdc++.h>
using namespace std;
#define exp 1e-7
ifstream f("gradina.in");
ofstream g("gradina.out");
int n,m;
struct pct
{
    int x,y,p;
} v[251];
double mn=1e9;
vector<pct>a,b;
bool viz[500];
int st[500];
char sol[500];
char sol1[500];
bool cmp(pct X,pct Y)
{
    if(X.x==Y.x)
        return X.y<Y.y;
    return X.x<Y.x;
}
int det(pct a,pct b,pct c)
{
    return (b.y-a.y)*(c.x-a.x)-(c.y-a.y)*(b.x-a.x);
}
bool check_bth()
{
    for(int i=0; i<=n; i++)
        viz[i]=false;
    int n=a.size()-1;
    int m=b.size()-1;
    st[1]=0;
    st[2]=1;
    int vf=2;
    viz[2]=true;
    for(int i=2; i<=n; i++)
    {
        while(vf>1&&det(a[st[vf-1]],a[st[vf]],a[i])<0)
        {
            viz[st[vf]]=false;
            vf--;
        }
        st[++vf]=i;
        viz[i]=true;
    }
    for(int i=n; i>=0; i--)
    {
        if(viz[i]==false)
        {
            while(vf>1&&det(a[st[vf-1]],a[st[vf]],a[i])<0)
            {
                viz[st[vf]]=false;
                vf--;
            }
            st[++vf]=i;
            viz[i]=true;
        }
    }
    if(vf!=n+2)
        return 0;
    pct r[300];
    for(int i=1;i<=n+1;i++)
        r[i]=a[st[i]];
    for(int i=1;i<=n+1;i++)
        a[i-1]=r[i];
    for(int i=0; i<=n; i++)
        viz[i]=false;
    st[1]=0;
    st[2]=1;
    vf=2;
    viz[2]=true;
    for(int i=2; i<=m; i++)
    {
        while(vf>1&&det(b[st[vf-1]],b[st[vf]],b[i])<0)
        {
            viz[st[vf]]=false;
            vf--;
        }
        st[++vf]=i;
        viz[i]=true;
    }
    for(int i=m; i>=0; i--)
    {
        if(viz[i]==false)
        {
            while(vf>1&&det(b[st[vf-1]],b[st[vf]],b[i])<0)
            {
                viz[st[vf]]=false;
                vf--;
            }
            st[++vf]=i;
            viz[i]=true;
        }
    }
    if(vf!=m+2)
        return 0;
    for(int i=1;i<=m+1;i++)
        r[i]=b[st[i]];
    for(int i=1;i<=m+1;i++)
        b[i-1]=r[i];
    return 1;
}
double triunghi(pct a,pct b,pct c)
{
    return det(a,b,c);
}
double polig(vector <pct>z)
{
    z.push_back(z[0]);
    double S=0;
    for(int i=1;i<z.size()-1;i++)
        S=S+det(z[0],z[i],z[i+1]);
  //  g<<S<<" ";
    return S/2.0;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i].x>>v[i].y,v[i].p=i;
    sort(v+1,v+n+1,cmp);
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            a.clear();
            b.clear();
            for(int k=1; k<=n; k++)
            {
                int R=det(v[i],v[j],v[k]);
                if(R<0)
                    a.push_back(v[k]);
                else
                    b.push_back(v[k]);
            }
            bool ok=false;
            if(a.size()>2&&b.size()>2)
            {
                if(!check_bth())
                    continue;
            /*    for(auto x: a)
                    g<<x.x<<" "<<x.y<<" "<<x.p<<'\n';
                g<<'\n';
                for(auto x : b)
                    g<<x.x<<" "<<x.y<<" "<<x.p<<'\n';
                g<<'\n'<<'\n'; */
                double aria_A=polig(a);
              //  g<<'\n';
                double aria_B=polig(b);

                int S=fabs(aria_A-aria_B);
              //  g<<S<<"DA"<<'\n';
                if(S<mn-exp)
                {
                    mn=S;
                    for(auto x: a)
                        if(x.p==1)
                            ok=true;
                    if(ok)
                    {
                        for(auto x : a )
                            sol[x.p]='I';
                        for(auto x: b)
                            sol[x.p]='V';
                    }
                    else
                    {
                        for(auto x : a )
                            sol[x.p]='V';
                        for(auto x: b)
                            sol[x.p]='I';
                    }
                }
                else
                if(fabs(S-mn)<exp)
                {
                    for(auto x: a)
                        if(x.p==1)
                            ok=true;
                    if(ok)
                    {
                        for(auto x : a )
                            sol1[x.p]='I';
                        for(auto x: b)
                            sol1[x.p]='V';
                    }
                    else
                    {
                        for(auto x : a )
                            sol1[x.p]='V';
                        for(auto x: b)
                            sol1[x.p]='I';
                    }
                    for(int i=1;i<=n;i++)
                    {
                        if(sol1[i]=='I'&&sol[i]=='V')
                        {
                            for(int i=1;i<=n;i++)
                                sol[i]=sol1[i];
                            break;
                        }
                        else
                        if(sol1[i]=='V'&&sol[i]=='I')
                            break;
                    }
                }
            }
        }
    g<<fixed<<setprecision(1)<<mn<<'\n';
    for(int i=1;i<=n;i++)
        g<<sol[i];
    return 0;
}