Cod sursa(job #589358)

Utilizator iepurasu_pasteGeorge Macovei iepurasu_paste Data 11 mai 2011 22:16:15
Problema Gradina Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define pi pair<pair<int,int>,int>
#define x first.first
#define y first.second
#define ind second
#define NMAX 304

double INF=(double)1000000000*1000000000;
double sol=INF;
char viz[NMAX],p[NMAX],vec[NMAX];
pi v[NMAX],vp[NMAX];
int st[NMAX],n,vecc[NMAX];

inline int cmp(const pi& a,const pi& b)
{
    return a.y<b.y;
}

inline int semn(pi A,pi B,pi C)
{
    int a=A.y-B.y;
    int b=B.x-A.x;
    int c=B.y*A.x-A.y*B.x;
    return C.x*a+C.y*b+c;
}

double infas(int tip)
{
    int nr=0,i,sf;
    for(i=1;i<=n;i++)
        if(p[i]==tip)
            vp[++nr]=v[i];
    if(nr<3)
        return INF;
    st[1]=1;st[2]=2;
    sf=2;
    for(i=3;i<=nr;i++)
    {
        while(sf>1 && semn(vp[st[sf-1]],vp[st[sf]],vp[i])<0)
            sf--;
        st[++sf]=i;
    }
    memset(viz,0,sizeof(viz));
    for(i=1;i<=sf;i++)
        viz[st[i]]=1;
    viz[st[1]]=0;
    for(i=nr;i>=1;i--)
        if(!viz[i])
        {
            while(sf>1 && semn(vp[st[sf-1]],vp[st[sf]],vp[i])<0)
                sf--;
            st[++sf]=i;
        }
    double arie=0;
    for(i=1;i<sf;i++)
        arie+=((double)vp[st[i]].x-vp[st[i+1]].x)
        *(vp[st[i]].y+vp[st[i+1]].y)/2;
    if(arie>0)
        return arie;
    return -arie;
}

int main ()
{
    int i,j,k;
    double s1,s2;
    
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
        v[i].y+=50000000;
        v[i].ind=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                for(k=1;k<=n;k++)
                    if(k!=i && k!=j)
                        if(semn(v[i],v[j],v[k])<0)
                            p[k]=0;
                        else
                            p[k]=1;
                p[i]=0;
                p[j]=1;
                s1=infas(0);
                s2=infas(1);
                if(s1==INF || s2==INF)
                    continue;
                s1-=s2;if(s1<0) s1=-s1;
                for(k=1;k<=n;k++)
                    vecc[v[k].ind]=p[k];
                if(s1==sol)
                {
                    int schimb=0;
                    for(k=1;k<=n;k++)
                        if(vecc[k]<vec[k])
                        {
                            schimb=1;
                            break;
                        }
                        else if(vecc[k]>vec[k])
                            break;
                    if(schimb==1)
                        for(k=1;k<=n;k++)
                            vec[k]=vecc[k];

                }
                if(s1<sol)
                {
                    sol=s1;
                    for(k=1;k<=n;k++)
                        vec[v[k].ind]=p[k];
                }
            }
    printf("%.1lf\n",sol);
    for(i=1;i<=n;i++)
        if(vec[i])
            printf("V");
        else
            printf("I");
    printf("\n");
    return 0;
}