Cod sursa(job #94180)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 21 octombrie 2007 21:07:37
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.53 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define NMAX 255
#define x first
#define y second

vector<pair<int,int> > P;
int N, H[NMAX], inH[NMAX], X[NMAX], Y[NMAX], Sol[NMAX], I[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", &a, &b);
                P.push_back(make_pair(a,b));
                I[i] = i;
        }
        for (a = 0; a < N; a++)
            for (b = a+1; b < N; b++)
                if ((P[a].x>P[b].x)||((P[b].x==P[a].x)&&(P[a].y>P[b].y)))
                {
                        i = P[a].x; P[a].x = P[b].x; P[b].x = i;
                        i = P[a].y; P[a].y = P[b].y; P[b].y = i;
                        i = I[a]; I[a] = I[b]; I[b] = i;
                }
}

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

        return (x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3);
}

long double hull()
{
        int i, nH = 0, n1 = 0;
        long double arie=0;

        for (i = 0; i < N && nH<2; i++)
            if (X[i]) n1++, H[nH++] = i, inH[i] = 1;
        for (; i < N; i++)
            if (X[i])
            {
                while ((nH>1)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
                H[nH++] = i; inH[i] = 1;
                n1++;
            }
        if (n1<3) return BIG;
        for (i = N-1; i >= 0; i--)
            if (X[i]&&!inH[i])
            {
                while ((nH>1)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
                H[nH++] = i; inH[i] = 1;
            }

        if ((nH<2)&&(cross(H[nH-2], H[nH-1], i)<=0)) inH[ H[--nH] ] = 0;
        H[nH] = H[0];

        if (nH<n1) return BIG;

        for (i = 0; i < nH; i++)
            arie += (long double)(P[ H[i] ].x*P[ H[i+1] ].y-P[ H[i+1] ].x*P[ H[i] ].y);

        return 0.5*fabs(arie);
}

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

        BIG=a*a; Dmin = BIG;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                for (k = 0; k < N; k++)
                {
                    X[k] = 0;
                    if (cross(i,j,k)<0) X[k] = 1;
                }
                X[i] = 1;
                s1 = hull();
                if (s1==BIG) s2 = 0;
                else {
                for (k = 0; k < N; k++) X[k] ^= 1, Y[k] = X[k];
                s2 = hull(); }
                dpart = fabs(s1-s2);
                if (s2==BIG) dpart = BIG;

                for (k = 0; k < N; k++)
                {
                    X[k] = 0;
                    if (cross(i,j,k)<0) X[k] = 1;
                }
                X[j] = 1;
                s1 = hull();
                if (s1==BIG) s2 = 0;
                else {
                for (k = 0; k < N; k++) X[k] ^= 1;
                s2 = hull(); }

                if (s2==BIG) s1 = 2*BIG;

                if (fabs(s1-s2)<dpart)
                {
                        if (fabs(s1-s2)<Dmin)
                        {
                                Dmin = fabs(s1-s2);
                                for (k = 0; k < N; k++) Sol[I[k]] = X[k];
                        }
                        else
                            if (fabs(s1-s2)==Dmin)
                            {
                                for (k = 0; k < N && Sol[I[k]]==X[k];k++);
                                if (X[k]<Sol[k])
                                   for (; k < N; k++) Sol[I[k]] = X[k];
                            }
                }
                if (dpart<Dmin)
                {
                        Dmin = dpart;
                        for (k = 0; k < N; k++) Sol[I[k]] = Y[k];
                }
                else
                    if (dpart==Dmin)
                    {
                        for (k = 0; k < N && Sol[I[k]]==Y[k];k++);
                        if (Y[k]<Sol[k])
                           for (; k < N; k++) Sol[I[k]] = Y[k];
                    }
            }
}

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

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