Cod sursa(job #1096549)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 februarie 2014 12:17:10
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <cstring>
#define EPS 1e-10

using namespace std;

const int N=255;

struct PII
{
    double x, y;
    int poz;
    bool operator<(const PII &e) const
    {
        return (x==e.x?y<e.y:x<e.x);
    }
};

PII a[N];
bitset <N> v;
int inf[N], p[2][N];
char soli[N], aux[N];

double modul(double k)
{
    if(k<0) return -k;
    return k;
}

double sarr(PII o, PII a, PII b)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

double geta(int u)
{
    double ret=0;
    int n=p[u][0], i, sign=1;
    inf[0]=2; inf[1]=p[u][1]; inf[2]=p[u][2];
    v.reset();
    v[p[u][2]]=1;
    for(i=3;i;i+=sign)
    {
        if(!v[p[u][i]])
        {
            while(inf[0]>1&&sarr(a[inf[inf[0]-1]], a[inf[inf[0]]], a[p[u][i]])<0)
            {
                v[inf[inf[0]--]]=0;
            }
            inf[++inf[0]]=p[u][i];
            v[p[u][i]]=1;
        }
        if(i==n) sign=-1;
    }
    for(i=1;i<inf[0];i++)
    {
        ret+=a[inf[i]].x*a[inf[i+1]].y-a[inf[i]].y*a[inf[i+1]].x;
    }
    return ret/2;
}

int main()
{
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);
    int n, i, j, k, l;
    double arie1, arie2, sol=1e19L;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
    {
        scanf("%lf%lf", &a[i].x, &a[i].y);
        a[i].poz=i;
    }
    sort(a+1, a+n+1);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i==j) continue;
            p[0][0]=p[1][0]=0;
            for(k=1;k<=n;k++)
            {
                if(k==i)
                {
                    p[0][++p[0][0]]=k;
                }
                else if(k==j)
                {
                    p[1][++p[1][0]]=k;
                }
                else if(sarr(a[k], a[i], a[j])>0) p[0][++p[0][0]]=k;
                else p[1][++p[1][0]]=k;
            }
            if(p[0][0]<3||p[1][0]<3) continue;
            arie1=geta(0);
            arie2=geta(1);
            if(modul(arie1-arie2)<sol)
            {
                sol=modul(arie1-arie2);
                for(l=1;l<=p[0][0];l++) soli[a[p[0][l]].poz]='I';
                for(l=1;l<=p[1][0];l++) soli[a[p[1][l]].poz]='V';
            }
            else if(modul(modul(arie1-arie2)-sol)<EPS)
            {
                for(l=1;l<=p[0][0];l++) aux[a[p[0][l]].poz]='I';
                for(l=1;l<=p[1][0];l++) aux[a[p[1][l]].poz]='V';
                for(l=1;l<=n;l++)
                {
                    if(soli[l]<aux[l]) break;
                    else if(soli[l]>aux[l])
                    {
                        memcpy(soli, aux, sizeof(aux));
                        break;
                    }
                }
            }
        }
    }
    printf("%.1lf\n%s", sol, soli+1);
}