Cod sursa(job #1096927)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 februarie 2014 18:54:31
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <cstring>

using namespace std;

const int N=255;

struct PII
{
    int 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], aux1[N];

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

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

long long geta(int u)
{
    long long 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+=(1LL*a[inf[i]].x*a[inf[i+1]].y-1LL*a[inf[i]].y*a[inf[i+1]].x);
    }
    return modul(ret);
}

int main()
{
    freopen("gradina.in", "r", stdin);
    freopen("gradina.out", "w", stdout);
    int n, i, j, k, l, solii=0, solj=0;
    long long arie1, arie2, sol=1LL<<62;
    scanf("%d", &n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].poz=i;
    }
    sort(a+1, a+n+1);
    soli[0]=aux[0]=aux1[0]='!';
    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)
                {
                    if(i<j) p[0][++p[0][0]]=k, aux[a[k].poz]='I', aux1[a[k].poz]='V';
                    else p[1][++p[1][0]]=k, aux[a[k].poz]='V', aux1[a[k].poz]='I';
                }
                else if(k==j)
                {
                    if(i<j) p[1][++p[1][0]]=k, aux[a[k].poz]='V', aux1[a[k].poz]='I';
                    else p[0][++p[0][0]]=k, aux[a[k].poz]='I', aux1[a[k].poz]='V';
                }
                else if(sarr(a[k], a[i], a[j])>0) p[0][++p[0][0]]=k, aux[a[k].poz]='I', aux1[a[k].poz]='V';
                else p[1][++p[1][0]]=k, aux[a[k].poz]='V', aux1[a[k].poz]='I';
            }
            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);
                solii=i;
                solj=j;
                if(strcmp(aux, aux1)<0) memcpy(soli, aux, sizeof(aux));
                else memcpy(soli, aux1, sizeof(aux1));
            }
            else if(modul(arie1-arie2)==sol)
            {

                if(strcmp(aux, soli)<0) memcpy(soli, aux, sizeof(aux)), solii=i, solj=j;
                if(strcmp(aux1, soli)<0) memcpy(soli, aux1, sizeof(aux1)), solii=i, solj=j;
            }
        }
    }
    printf("%.1lf\n%s\n", 1.0*sol/2, soli+1);
    //fprintf(stderr, "%d %d\n", solii, solj);
}