Cod sursa(job #1466454)

Utilizator enedumitruene dumitru enedumitru Data 29 iulie 2015 11:22:02
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define CLEAR(x) memset(x, 0, sizeof(x))
#define ll long long
#define INF 900000000
#define NMax 405
using namespace std;
typedef struct {int x,y,ord;} punct;
typedef punct point_set[NMax];
int N;
point_set v, A, B;
ll bst=(ll)INF*INF;
char SOL[NMax],Res[NMax];
int cmp(const punct& a, const punct& b)
{   return (a.y<b.y)||(a.y==b.y && a.x<b.x);}
int semn(punct A, punct B, punct C)
{   ll a=A.y-B.y,b=B.x-A.x,c =(ll)A.x*B.y-(ll)B.x*A.y;
    ll E=(ll)a*C.x+(ll)b*C.y+c;
    if(E<0) return -1;
    if(E>0) return +1;
    return 0;
}
ll area(punct A, punct B, punct C)
{   ll E=((ll)(B.x-A.x))*((ll)(C.y-A.y))-((ll)(C.x-A.x))*((ll)(B.y - A.y));
    if(E<0) E=-E;
    return E;
}
int st[NMax],uz[NMax];
ll ConvexHull(point_set X, int nr) // returneaza 0 daca X nu e poligon convex sau dublul ariei lui daca este
{   int i,k,pas=+1; ll S=0;
    if(nr<3) return 0;
    CLEAR(st); CLEAR(uz);
    st[1]=1; st[2]=2; uz[2]=1; k=2; i=2;
    while(!uz[1])
    {   while(uz[i])
        {   i+=pas;
            if(i==nr) pas=-1;
        }
        while(k>=2 && semn(X[st[k-1]],X[st[k]],X[i])<0) uz[st[k--]]=0;
        st[++k]=i; uz[i]=1;
    }
    st[k--]=0;
    if(nr==k)
    {   for(i=1,S=0;i<=nr-2;i++) S+=area(X[st[1]],X[st[i+1]],X[st[i+2]]);
        return S;
    }
    return 0;
}
int main(void)
{   int i,j,k,E,p1,p2; ll S1,S2,diff;
    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].ord=i;}
    sort(v+1,v+N+1,cmp);
    for(i=0;i<=N;i++) SOL[i]='Z';
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
        {   if(i==j) continue;
            for(k=1,p1=0,p2=0;k<= N;k++)
                if(k!=i&&k!=j)
                {   E=semn(v[i],v[j],v[k]);
                    if(E>0) A[++p1]=v[k]; else if(E<0) B[++p2]=v[k];
                }
                else if(k==i) A[++p1]=v[i]; else if(k==j) B[++p2]=v[j];
            if(i==4&&j==5) k=0;
            S1=ConvexHull(A,p1);
            if(!S1) continue;
            S2=ConvexHull(B,p2);
            if(!S2) continue;
            diff=S1-S2;
            if(diff<0) diff=-diff;
            if(diff<=bst)
            {   bst=diff;
                for(k=0;k<=N;k++) Res[k]=' ';
                for(k=1;k<=p1;k++) Res[A[k].ord]='I';
                for(k=1;k<=p2;k++) Res[B[k].ord]='V';
                if(Res[1]=='V') for(k=1;k<=N; k++) if(Res[k]=='I') Res[k]='V'; else Res[k] = 'I';
                for(k=1,E=0;k<=N;k++) if(SOL[k]>Res[k]) {E=1; break;}
                if(E) for(k=1;k<=N;k++) SOL[k]=Res[k];
            }
        }
    printf("%.1lf\n",((double)bst)*0.5);
    for(i=1;i<=N;i++) printf("%c",SOL[i]);
    printf("\n");
    return 0;
}