Cod sursa(job #3247302)

Utilizator tudorhTudor Horobeanu tudorh Data 6 octombrie 2024 21:25:42
Problema Gradina Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
char r[250],crt[250];
long long mini=LONG_LONG_MAX;
int n;
struct Punct
{
    long long x,y;
    int index;
    bool t,side;
} pct[250];
vector <Punct> s0,s1;
bool sortpct(Punct a, Punct b)
{
    return(a.x<b.x || (a.x==b.x && a.y<b.y));
}
long long Arie(Punct a,Punct b,Punct c)
{
    return (a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
bool lexcomp(char a[],char b[])
{
    for(int i=0;i<n;i++)
        if(a[i]>b[i])
            return 0;
        else if(a[i]<b[i])
            return 1;
    return 1;
}
void infasuratoare()
{
    s0.clear(),s1.clear();
    for(int i=0; i<n; i++)
        pct[i].t=0;
    int s0p0=-1,s0p1=-1,s1p0=-1,s1p1=-1;
    for(int i=0; i<n; i++)
        if(pct[i].side==0)
        {
            if(s0p0==-1)
                s0p0=i;
            s0p1=i;
        }
        else
        {
            if(s1p0==-1)
                s1p0=i;
            s1p1=i;
        }
    for(int i=0; i<n; i++)
        if(pct[i].side==0)
        {
            if(i==s0p0 || i==s0p1)
                continue;
            long long arie=Arie(pct[s0p0],pct[s0p1],pct[i]);
            pct[i].t=(arie>0);
        }
        else
        {
            if(i==s1p0 || i==s1p1)
                continue;
            long long arie=Arie(pct[s1p0],pct[s1p1],pct[i]);
            pct[i].t=(arie>0);
        }
    for(int i=0; i<n; i++)
        if(pct[i].side==0)
        {
            if(pct[i].t)
                continue;
            while(s0.size()>=2)
            {
                long long arie=Arie(s0[s0.size()-2],s0[s0.size()-1],pct[i]);
                if(arie<0)
                    return;
                else break;
            }
            s0.push_back(pct[i]);
        }
        else
        {
            if(pct[i].t)
                continue;
            while(s1.size()>=2)
            {
                long long arie=Arie(s1[s1.size()-2],s1[s1.size()-1],pct[i]);
                if(arie<0)
                    return;
                else break;
            }
            s1.push_back(pct[i]);
        }
    int s0size0=s0.size()-1,s1size0=s1.size()-1;
    pct[s0p0].t=pct[s1p0].t=1;
    for(int i=n-1; i>=0; i--)
        if(pct[i].side==0)
        {
            if(!pct[i].t)
                continue;
            while(s0.size()-s0size0>=2)
            {
                long long arie=Arie(s0[s0.size()-1],s0[s0.size()-2],pct[i]);
                if(arie>0)
                    return;
                else break;
            }
            s0.push_back(pct[i]);
        }
        else
        {
            if(!pct[i].t)
                continue;
            while(s1.size()-s1size0>=2)
            {
                long long arie=Arie(s1[s1.size()-1],s1[s1.size()-2],pct[i]);
                if(arie>0)
                    return;
                else break;
            }
            s1.push_back(pct[i]);
        }
    long long arie0=0,arie1=0;
    if(s0.size())
    {
        s0.pop_back();
        for(int i=1; i<s0.size()-1; i++)
            arie0+=abs(Arie(s0[i],s0[i+1],s0[0]));
    }
    if(s1.size())
    {
        s1.pop_back();
        for(int i=1; i<s1.size()-1; i++)
            arie1+=abs(Arie(s1[i],s1[i+1],s1[0]));
    }
    if(abs(arie0-arie1)<mini)
    {
        mini=abs(arie0-arie1);
        for(int i=0;i<n;i++)
            if(pct[i].side==0)
                r[pct[i].index]='I';
            else r[pct[i].index]='V';

        for(int i=0;i<n;i++)
            if(pct[i].side==0)
                crt[pct[i].index]='V';
            else crt[pct[i].index]='I';
        if(!lexcomp(r,crt))
            strcpy(r,crt);
    }
    else if(abs(arie0-arie1==mini))
    {
        for(int i=0;i<n;i++)
            if(pct[i].side==0)
                crt[pct[i].index]='I';
            else crt[pct[i].index]='V';
        if(!lexcomp(r,crt))
            strcpy(r,crt);
        for(int i=0;i<n;i++)
            if(pct[i].side==0)
                crt[pct[i].index]='V';
            else crt[pct[i].index]='I';
        if(!lexcomp(r,crt))
            strcpy(r,crt);
    }
}
void dreapta(int p1,int p2)
{
    for(int i=0; i<n; i++)
    {
        if(i==p1 || i==p2)
            continue;
        long long arie=Arie(pct[p1],pct[p2],pct[i]);
        pct[i].side=(arie>0);
    }
    ///0 0
    infasuratoare();
    pct[p1].side=1;
    ///1 0
    infasuratoare();
    pct[p1].side=0;
    pct[p2].side=1;
    ///0 1
    infasuratoare();
    pct[p1].side=pct[p2].side=1;
    ///1 1
    infasuratoare();
    pct[p1].side=pct[p2].side=0;
}
int main()
{
    int x,y;
    fin>>n;
    for(int i=0; i<n; i++)
    {
        fin>>x>>y;
        pct[i]= {x,y};
        pct[i].index=i;
    }
    sort(pct,pct+n,sortpct);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
        {
            dreapta(i,j);
            //cout<<i<<" "<<j<<endl;
        }
    fout<<fixed<<setprecision(1)<<(float)mini/2<<setprecision(0)<<'\n'<<r;
    return 0;
}