Cod sursa(job #74033)

Utilizator astronomyAirinei Adrian astronomy Data 23 iulie 2007 14:31:36
Problema Gradina Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.9 kb
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define pb push_back
#define mp make_pair
#define x first
#define y second
#define MAX_N 256
#define INF (1 << 30)
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))

typedef long long llong;

int N, F, AUX[MAX_N];
vector< pair<int, int> > P;
vector<int> G[MAX_N];

llong res;
string conf;

int cross(int i, int j, int k) // P[i]P[j] x P[i]P[k]
{
    llong t = (llong)(P[j].x-P[i].x)*(P[k].y-P[i].y)-(llong)(P[k].x-P[i].x)*
    (P[j].y-P[i].y);
    return t > 0 ? 1 : -1;
}

llong det(int i, int j, int k)
{
    return (llong)(P[j].x-P[i].x)*(P[k].y-P[i].y)-(llong)(P[k].x-P[i].x)*
    (P[j].y-P[i].y);
}

int cmp(int i, int j)
{
    return cross(F, i, j) > 0;
}

void preproc(void)
{
    int i, j;

    for(i = 0; i < N; i++)
    {
        for(j = 0; j < N; j++)
         if(P[j].y > P[i].y || (P[j].y == P[i].y && P[j].x > P[i].x))
            G[i].pb(j);
        F = i;
        sort(G[i].begin(), G[i].end(), cmp);
    }
}

llong calc(vector<int> V)
{
    int i, ind, j, ymin = INF, xmin;
    llong area;
    char used[MAX_N];

    vector<int>::iterator it;
    
    memset(used, 0, sizeof(used));

    for(it = V.begin(); it != V.end(); ++it)
    {
        used[*it] = 1;
        if( P[*it].y < ymin || (P[*it].y == ymin && P[*it].x < xmin))
            xmin = P[*it].x, ymin = P[*it].y, ind = *it;
    }
    
    for(AUX[j = 1] = ind, it = G[ind].begin(); it != G[ind].end(); ++it)
     if(used[*it])
        AUX[++j] = *it;

    for(area = 0, i = 3; i <= j; i++)
    {
        if( cross(AUX[i-2], AUX[i], AUX[i-1]) == 1 )
            return -1;
        area += abs( det(AUX[1], AUX[i], AUX[i-1]) );
    }

    if(j >= 3)
        return area;
    else
        return -1;
}

void solve(void)
{
    int i, j, k, ax1, ax2, sgn;
    llong r1, r2, b;
    string c, c2;
    vector<int> V, V2;

    for(i = 0; i < N; i++)
     for(j = i+1; j < N; j++)
     {
        // -1 cu i, +1 cu j
        for(V.clear(), V.pb(i), V2.clear(), V2.pb(j), k = 0; k < N; k++)
         if( k != i && k != j )
         {
            if( cross(i, j, k) == -1 )
                V.pb(k);
            else
                V2.pb(k);
         }

        r1 = calc(V);
        if(r1 == -1)
            continue ;

        r2 = calc(V2);
        if(r2 == -1)
            continue ;

        if(j != 0 && (i == 0 || cross(i, j, 0) == -1) )
        {
            for(c.clear(), k = 0; k < N; k++)
             if(k != j && (k == i || cross(i, j, k) == -1) )
                c.pb('I');
            else
                c.pb('V');
        }
        else
        {
            for(c.clear(), k = 0; k < N; k++)
             if(k != j && (k == i || cross(i, j, k) == -1) )
                c.pb('V');
            else
                c.pb('I');
        }

        if(r1 >= 0 && r2 >= 0)
        {
            b = MAX(r1, r2) - MIN(r1, r2);
            if(b < res || (b == res && c < conf))
                res = b, conf = c;
        }
     }

    for(i = 0; i < N; i++)
     for(j = i+1; j < N; j++)
     {
        // +1 cu i, -1 cu j
        for(V.clear(), V.pb(j), V2.clear(), V2.pb(i), k = 0; k < N; k++)
         if( k != i && k != j )
         {
            if( cross(i, j, k) == -1 )
                V.pb(k);
            else
                V2.pb(k);
         }

        r1 = calc(V);
        if(r1 == -1)
            continue ;

        r2 = calc(V2);
        if(r2 == -1)
            continue ;

        if(i != 0 && (j == 0 || cross(i, j, k) == -1))
        {
            for(c.clear(), k = 0; k < N; k++)
             if(k != i && (k == j || cross(i, j, k) == -1) )
                c.pb('I');
            else
                c.pb('V');
        }
        else
        {
            for(c.clear(), k = 0; k < N; k++)
             if(k != i && (k == j || cross(i, j, k) == -1) )
                c.pb('V');
            else
                c.pb('I');
        }
        
        if(r1 >= 0 && r2 >= 0)
        {
            b = MAX(r1, r2) - MIN(r1, r2);
            if(b < res || (b == res && c < conf))
                res = b, conf = c;
        }
     }
}

void ruleaza(void)
{
    int i, a, b;

    scanf("%d\n", &N);

    for(i = 1; i <= N; i++)
    {
        scanf("%d %d\n", &a, &b);
        P.pb( mp(a,b) );
    }

    preproc();
    res = (llong)(1<<30)*(1<<30);
    solve();

    printf("%lld.%c\n", res/2, res%2 ? '5' : '0');
    cout << conf << '\n';
}

int main(void)
{
    freopen("gradina.in", "rt", stdin);
    freopen("gradina.out", "wt", stdout);

    ruleaza();

    return 0;
}