Cod sursa(job #1053175)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 12 decembrie 2013 14:44:44
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include<cstdio>
#include<algorithm>
#include<utility>
#include<cstring>

#define NMAX 255

using namespace std;

typedef pair<pair<int,int>,int> PIII;

int N,I,J,U1,U2;
PIII V[NMAX],P[NMAX],Q[NMAX];
int H1[NMAX],H2[NMAX];
bool viz[NMAX];
char S[NMAX],SOL[NMAX];
long long x,sol=1LL<<62;

inline int cross_product(PIII A,PIII B,PIII C) {return (B.first.first-A.first.first)*(C.first.second-A.first.second) - (B.first.second-A.first.second)*(C.first.first-A.first.first);}

void convex_hull(PIII P[NMAX],int N,int H[NMAX],int &M)
{
    int i;
    M=0;
    memset(viz,0,sizeof(viz));
    for(i=1;i<=N;i++)
    {
        for(;M>=2;)
        {
            if(cross_product(P[H[M-1]],P[H[M]],P[i])>0) M--;
            else break;
        }
        H[++M]=i;
    }
    for(i=1;i<=M;i++) viz[H[i]]=1;
    viz[H[1]]=0;
    for(i=N;i>=1;i--)
    {
        if(viz[i]) continue;
        for(;M>=2;)
        {
            if(cross_product(P[H[M-1]],P[H[M]],P[i])>0) M--;
            else break;
        }
        H[++M]=i;
    }
    M--;
}

long long area(PIII P[NMAX],int H[NMAX],int M)
{
    int i;
    long long S=0;
    for(i=1;i<=M;i++)
        S+=(1LL*P[H[i]].first.first*P[H[i+1]].first.second - 1LL*P[H[i+1]].first.first*P[H[i]].first.second);
    if(S<0) S=-S; i--;
    return S;
}

void update()
{
    int i;
    char a='I',b='V';
    if(U1+U2<N) return;

    for(i=1;i<=U2;i++)
        if(Q[H2[i]].second==1) {swap(a,b); break;}

    for(i=1;i<=U1;i++) S[P[H1[i]].second]=a;
    for(i=1;i<=U2;i++) S[Q[H2[i]].second]=b;

    x=area(P,H1,U1)-area(Q,H2,U2);
    if(x<0) x=-x;
    if(x<sol)
    {
        sol=x;
        strcpy(SOL+1,S+1);
        return;
    }
    if(x==sol && strcmp(S+1,SOL+1)<0)
    {
        strcpy(SOL+1,S+1);
        return;
    }
}

int main()
{
    int a,b,i,j,k;
    freopen("gradina.in","r",stdin);
    freopen("gradina.out","w",stdout);

    scanf("%d",&N);
    for(i=1;i<=N;i++)
    {
        scanf("%d%d",&a,&b);
        V[i]=make_pair(make_pair(a,b),i);
    }
    sort(V+1,V+N+1);

    for(i=1;i<=N;i++)
        for(j=i+1;j<=N;j++)
        {
            I=J=0;

            for(k=1;k<=N;k++)
            {
                if(k==i) {P[++I]=V[k]; continue;}
                if(k==j) {Q[++J]=V[k]; continue;}
                if(cross_product(V[i],V[j],V[k])<0) P[++I]=V[k];
                else Q[++J]=V[k];
            }

            if(I<3 || J<3) continue;

            convex_hull(P,I,H1,U1);
            convex_hull(Q,J,H2,U2);
            update();

            I=J=0;

            for(k=1;k<=N;k++)
            {
                if(k==j) {P[++I]=V[k]; continue;}
                if(k==i) {Q[++J]=V[k]; continue;}
                if(cross_product(V[i],V[j],V[k])<0) P[++I]=V[k];
                else Q[++J]=V[k];
            }

            if(I<3 || J<3) continue;

            convex_hull(P,I,H1,U1);
            convex_hull(Q,J,H2,U2);

            update();
        }
    printf("%.1lf\n",sol/2.0);
    printf("%s\n",SOL+1);
    return 0;
}