Cod sursa(job #2238645)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 6 septembrie 2018 19:36:49
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define MAXN 255
#define ll long long
using namespace std;
ifstream si("gradina.in");
ofstream so("gradina.out");
long long rez=-1;
int n,sol[2][MAXN];
char ans[MAXN],aux[MAXN];
struct myc
{
    int x,y,z;
    bool operator<(const myc u)const
    {
        if(x!=u.x)
            return x<u.x;
        else
            return y<u.y;
    }
}v[MAXN];
inline long long arie(int i,int j,int p)
{
    return 1LL*v[i].x*v[j].y-1LL*v[j].x*v[i].y+1LL*v[j].x*v[p].y-1LL*v[p].x*v[j].y+1LL*v[p].x*v[i].y-1LL*v[i].x*v[p].y;
}

inline long long convex(int r[])
{
    int a=0,b=1;
    long long ans=0;
    for(int i=2;i<r[0];i++)
    {
        if(arie(r[1],r[r[0]],r[i])>0)
        {
            if(a==0)
            {
                a=1;
                b=i;
            }
            else
            {
                if(arie(r[a],r[b],r[i])>0)
                    return 0;
                a=b;
                b=i;
                ans+=arie(r[1],r[b],r[a]);
            }
        }
    }
    if((a)&&(arie(r[a],r[b],r[r[0]])>0))
        return 0;
    a=b;
    b=r[0];
    if(a!=1)
        ans+=arie(r[1],r[b],r[a]);
    for(int i=r[0]-1;i>1;i--)
    {
        if(arie(r[1],r[r[0]],r[i])<0)
        {
            if(arie(r[a],r[b],r[i])>0)
                return 0;
            a=b;
            b=i;
            ans+=arie(r[1],r[b],r[a]);
        }
    }
    if(arie(r[a],r[b],r[1])>0)
        return 0;
    return ans;
}
void solutie()
{
    if(sol[0][0]<3)
        return;
    if(sol[1][0]<3)
        return;
    long long a1=convex(sol[0]);
    if(a1==0)
        return;
    long long a2=convex(sol[1]);
    if(a2==0)
        return;
    //cout<<a1<<' '<<a2;
    if((rez==-1)||(abs(a1-a2)<rez))
    {
        rez=abs(a1-a2);
        for(int i=1;i<=sol[0][0];i++)
            ans[v[sol[0][i]].z]='I';
        for(int i=1;i<=sol[1][0];i++)
            ans[v[sol[1][i]].z]='V';
        if(ans[0]=='V')
            for(int i=0;i<n;i++)
                if(ans[i]=='I')
                    ans[i]='V';
                else
                    ans[i]='I';
    }
    else
        if(abs(a1-a2)==rez)
        {
            for(int i=1;i<=sol[0][0];i++)
                aux[v[sol[0][i]].z]='I';
            for(int i=1;i<=sol[1][0];i++)
                aux[v[sol[1][i]].z]='V';
            if(aux[0]=='V')
                for(int i=0;i<n;i++)
                    if(aux[i]=='I')
                        aux[i]='V';
                    else
                        aux[i]='I';
            int p=0;
            while((p+1<n)&&(aux[p]==ans[p]))
                p++;
            if(aux[p]<ans[p])
            {
                while(p<n)
                {
                    ans[p]=aux[p];
                    p++;
                }
            }
    }
}
int main()
{
    si>>n;
    for(int i=0;i<n;++i)
    {
        si>>v[i].x>>v[i].y;
        v[i].z=i;
    }
    sort(v,v+n);
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
        {
            int l;
            sol[0][0]=sol[1][0]=0;
            for(int p=0;p<n;++p)
            {
                if(p!=i&&p!=j)
                {
                    l=(arie(i,j,p)>0);
                    //cout<<l<<'\n';
                    sol[l][++sol[l][0]]=p;
                }
                else
                    if(p==i)
                        sol[0][++sol[0][0]]=p;
                    else
                        sol[1][++sol[1][0]]=p;
            }
            solutie();
        }
    so<<setprecision(1)<<fixed<<rez*0.5<<'\n';
    for(int i=0;i<n;++i)
        so<<ans[i];
    return 0;
}