Nu aveti permisiuni pentru a descarca fisierul grader_test19.in

Cod sursa(job #93066)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 17 octombrie 2007 16:42:31
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.31 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define NMAX 255

struct point
{
        int x, y, ind;
};
point P[NMAX], V[NMAX];
int N, M, X[NMAX], St[NMAX], Sol[NMAX], inCH[NMAX], sol[NMAX];
long double Dmin, BIG;

void read()
{
        int i, a, b;
        freopen("gradina.in", "r", stdin);
        scanf("%d", &N);
        for (i = 0; i < N; i++)
        {
                scanf("%d%d", &P[i].x, &P[i].y);
                P[i].ind = i;
        }
}

void sort()
{
        int i, j, aux;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                if ( (P[i].x > P[j].x)||( (P[i].x==P[j].x)&&(P[i].y > P[j].y) ) )
                {
                   aux = P[i].x; P[i].x = P[j].x; P[j].x = aux;
                   aux = P[i].y; P[i].y = P[j].y; P[j].y = aux;
                   aux = P[i].ind; P[i].ind = P[j].ind; P[j].ind = aux;
                }
}

long long cross2(int a, int b, int c)
{
        long long x1 = V[a].x, x2 = V[b].x, x3 = V[c].x;
        long long y1 = V[a].y, y2 = V[b].y, y3 = V[c].y;
        long long d = (x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3);

        return d;
}

long double chull()
{
        int i, nst = 1;
        long double s=0;


        for (i = 0; i < M; i++) St[i] = 0;

        for (i = M = 0; i < N; i++)
            if (X[i]) V[M].x = P[i].x, V[M].y = P[i].y, V[M++].ind = P[i].ind;

        St[0] = 0; St[1] = 1;
        for (i = 2; i < M; i++)
        {
            while ( (nst>1) && (cross2(St[nst-1], St[nst], i)>=0) ) nst--;
            St[++nst] = i;
        }

        for (i = 0; i < N; i++) inCH[i] = 0;
        for (i = 0; i <= nst; i++) inCH[ St[i] ] = 1;

        for (i = M-1; i > 0; i--)
            if (!inCH[i])
            {
                while ( (nst>1) && (cross2(St[nst-1], St[nst], i)>=0) ) nst--;
                St[++nst] = i;
            }

        while ( (nst>2) && (cross2(St[nst-1], St[nst], St[0])>=0) ) nst--;
        St[++nst] = St[0];

        for (i = 0, s = 0; i < nst; i++)
            s = s+(V[ St[i] ].x*V[ St[i+1] ].y-V[ St[i+1] ].x*V[ St[i] ].y);

        if (s==0) s = 2*BIG;
        return fabs(s)*0.5;
}

long long cross(int a, int b, int c)
{
        long long x1 = P[a].x, x2 = P[b].x, x3 = P[c].x;
        long long y1 = P[a].y, y2 = P[b].y, y3 = P[c].y;
        long long d = (x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3);

        return d;
}

void solve()
{
        int i, j, k;
        long double s1=50000000, s2=50000000;

        BIG = s1*s2;
        Dmin = BIG;
        
        sort();

        for (i = 2; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                for (k = 0; k < N; k++) X[k] = 0;
                X[i] = 1;
                for (k = 0; k < N; k++)
                    if (cross(i,j,k)<0) X[k] = 1;
                s1 = chull();
                for (k = 0; k < N; k++) X[k] ^= 1;
                s2 = chull();
                if ((s1<BIG)&&(s2<BIG))
                {
                        s1 = fabs(s1-s2);
                        if (s1 < Dmin)
                        {
                           Dmin = s1;
                           for (k = 0; k < N; k++)
                               if (X[k]) Sol[ P[k].ind ] = 1;
                        }
                        else
                            if (s1==Dmin)
                            {
                                for (k = 0; k < N; k++)
                                    if (X[k]) sol[ P[k].ind ] = 1;
                                for (k = N-1; Sol[k] == sol[k] && k>=0; k--);
                                if (Sol[k]>sol[k])
                                   for (k = 0; k < N; k++) Sol[k] = sol[k];
                            }
                }

                for (k = 0; k < N; k++) X[k] = 0;
                X[j] = 1;
                for (k = 0; k < N; k++)
                    if (cross(i,j,k)<0) X[k] = 1;
                s1 = chull();
                for (k = 0; k < N; k++) X[k] ^= 1;
                s2 = chull();
                if ((s1<BIG)&&(s2<BIG))
                {
                        s1 = fabs(s1-s2);
                        if (s1 < Dmin)
                        {
                           Dmin = s1;
                           for (k = 0; k < N; k++) Sol[k] = 0;
                           for (k = 0; k < N; k++)
                               if (X[k]) Sol[ P[k].ind ] = 1;
                               
                        }
                        else
                            if (s1==Dmin)
                            {
                                for (k = 0; k < N; k++)
                                    if (X[k]) sol[ P[k].ind ] = 1;
                                for (k = N-1; Sol[k] == sol[k] && k>=0; k--);
                                if (Sol[k]>sol[k])
                                   for (k = 0; k < N; k++) Sol[k] = sol[k];
                            }
                }
            }
}

void write()
{
        freopen("gradina.out", "w", stdout);
        printf("%llf\n", Dmin);
        for (int i = 0; i < N; i++)
            if (!Sol[i]) printf("I");
            else printf("V");
        printf("\n");
}

int main()
{
        read();
        solve();
        write();
        return 0;
}