Cod sursa(job #2542442)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 9 februarie 2020 23:30:01
Problema Gradina Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <bits/stdc++.h>
#define ll long long
#define inf (1LL<<62)

using namespace std;

const int nmax=255;

struct pct
{
    int x,y,i;
}aux[nmax];

vector<pct>v,a,b;
vector<char>s;
int hull[nmax];
bool viz[nmax];

bool mycmp(pct a,pct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

ll cross(pct x,pct y,pct z)
{
    return (ll)(y.x-x.x)*(z.y-x.y)-(ll)(y.y-x.y)*(z.x-x.x);
}

void build_pcts(vector<pct>&a,vector<pct>&b,int poz1,int poz2,int n)
{
    a.clear();
    b.clear();
    for(int i=0; i<n; i++)
    {
        if(poz1==i)
            a.push_back(v[i]);
        if(poz2==i)
            b.push_back(v[i]);
        if(poz1!=i and poz2!=i)
            if(cross(v[poz1],v[poz2],v[i])>0)
                a.push_back(v[i]);
            else
                b.push_back(v[i]);
    }
}

void replace_sol(vector<char>&s,vector<pct>&a,vector<pct>&b,int n,bool iseq)
{
    vector<char>aux;
    aux.resize(n+1);
    for(pct x:a)
        aux[x.i]='I';
    for(pct y:b)
        aux[y.i]='V';
    if(aux[0]=='V')
        for(int i=0; i<n; i++)
            aux[i]=((aux[i]=='V')?'I':'V');
    if(iseq)
    {
        bool ok=false;
        for(int i=0; i<n; i++)
            if(aux[i]<s[i])
            {
                ok=true;
                break;
            }
            else if(aux[i]>s[i])
                break;
        if(ok==true)
            for(int i=0;i<n;i++)
                s[i]=aux[i];
    }
    else
    {
        for(int i=0; i<n;i++)
            s[i]=aux[i];
    }
}

ll area(vector<pct>&v)
{
    ll ans=0;
    for(int i=0;i<v.size();i++)
        ans+=cross({0,0,0},v[i],v[(i+1)%(int)v.size()]);
    return fabs(ans);
}

bool ok(vector<pct>&v)
{
    if(v.size()<=2)
        return 0;
    memset(viz,0,sizeof(viz));
    int dir=1,k=-1;
    for(int i=0;i>=0;i+=dir)
    if(!viz[i])
    {
        while(k>=1 and cross(v[hull[k-1]],v[hull[k]],v[i])<0)
            viz[hull[k--]]=0;
        hull[++k]=i;
        viz[i]=1;
        if(i==v.size()-1)
            dir=-1;
    }
    if(k+1!=v.size() or cross(v[hull[k-1]],v[hull[k]],v[0])<0)
        return 0;
    for(int i=0;i<v.size();i++)
        aux[i]=v[hull[i]];
    for(int i=0;i<v.size();i++)
        v[i]=aux[i];
    return 1;
}

int main()
{
    ifstream cin("gradina.in");
    ofstream cout("gradina.out");
    ll mn=inf;
    int n;
    cin>>n;
    v.resize(n);
    s.resize(n);
    for(int i=0; i<n; i++)
        cin>>v[i].x>>v[i].y,v[i].i=i;
    sort(v.begin(),v.end(),mycmp);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
        {
            build_pcts(a,b,i,j,n);
            if(ok(a) and ok(b))
            {
                if(fabs(area(a)-area(b))<=mn)
                {
                    replace_sol(s,a,b,n,(fabs(area(a)-area(b))==mn));
                    mn=fabs(area(a)-area(b));
                }
            }
        }
    cout<<fixed<<setprecision(1)<<mn/2.0<<"\n";
    for(int i=0;i<s.size();i++)
        cout<<s[i];
    return 0;
}