Cod sursa(job #903745)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 2 martie 2013 18:55:11
Problema Gradina Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, n1, n2;
double sol = 2000000000.0;
char s[256], ssol[256];
struct punct
{
    int x, y;
    double tg;
};
punct a[256], P1[256], P2[256], st[256];

inline void Read()
{
    freopen ("gradina.in", "r", stdin);
    scanf ("%d", &n);
    int i, x, y;
    for (i=1; i<=n; i++)
    {
        scanf ("%d %d", &x, &y);
        a[i].x = x;
        a[i].y = y;
		if (x==0)
			a[i].tg = 2000000000.0;
		else
			a[i].tg = (y*1.0) / (x*1.0);
    }
}

inline long long det(const punct X, const punct Y, const punct Z)
{
    // X.x X.y 1
    // Y.x Y.y 1
    // Z.x Z.y 1
    return 1LL*X.x*Y.y + 1LL*X.y*Z.x + 1LL*Y.x*Z.y - 1LL*Y.y*Z.x - 1LL*X.x*Z.y - 1LL*X.y*Y.x;
}

inline bool cmp (const punct A, const punct B)
{
    // y1 - y0 / x1 - x0 < y2 - y0 / x2 - x0
    // y1 - y0 * x2 - x0 < y2 - y0 * x1 - x0
    return A.tg < B.tg;
}

inline double Infasuratoare(punct *v, int nv)
{
    int poz, i, vf;
    poz = 1;
    for (i=2; i<=nv; i++)
    {
        if (v[i].y < v[poz].y || (v[i].y == v[poz].y && v[i].x < v[poz].x))
            poz = i;
    }
    swap (v[1], v[poz]);
    sort(v+2, v+nv+1, cmp);
    vf = 0;
    st[++vf] = v[1];
    st[++vf] = v[2];
    for (i=3; i<=nv; i++)
    {
        while (vf >= 2 && det(st[vf-1], st[vf], v[i]) <= 0)
            vf--;
        st[++vf] = v[i];
    }
    if (vf == nv)
    {
        double aria=0.0, x;
        for (i=2; i<nv; i++)
        {
            x = det(v[1], v[i], v[i+1]);
            if (x<0)
                x=-x;
            aria+=x;
        }
        return aria;
    }
    return -1;

}

inline void Solve()
{
    int i, j, k, ind;
    double a1, a2, dif;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (i==j)
                continue;
            n1 = 0, n2 = 0;
            s[i] = 'I';
            s[j] = 'V';
            n1++;
            P1[n1] = a[i];
            n2++;
            P2[n2] = a[j];
            for (k=1; k<=n; k++)
                if (i!=k && j!=k)
                {
                    if (det(a[i], a[j], a[k]) < 0)
                    {
                        n1++;
                        P1[n1] = a[k];
                        s[k] = 'I';
                    }
                    else
                    {
                        n2++;
                        P2[n2] = a[k];
                        s[k] = 'V';
                    }
                }
            if (n1 >= 3 && n2 >= 3)
            {
                a1 = Infasuratoare(P1, n1);
                a2 = Infasuratoare(P2, n2);
                if (a1 != -1 && a2 != -1)
                {
                    dif = (a1-a2);
                    if (dif < 0)
                        dif = -dif;
                    if (dif < sol)
                    {
                        sol = dif;
                        for (ind = 1; ind <= n; ind++)
                            ssol[ind] = s[ind];
                    }
                    else
                        if (dif == sol)
                        {
                            if (strcmp(s+1, ssol+1) < 0)
                                for (ind = 1; ind <= n; ind++)
                                    ssol[ind] = s[ind];
                        }
                }
            }
        }
    }
}

inline void Write()
{
    FILE*g = fopen("gradina.out", "w");
    fprintf (g, "%.1lf\n%s\n", (double)sol/2, ssol+1);
    fclose(g);
}

int main()
{
    Read();
    Solve();
    Write();

    return 0;
}