Cod sursa(job #74009)

Utilizator astronomyAirinei Adrian astronomy Data 23 iulie 2007 13:15:34
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.21 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);
}

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];
    memset(used, 0, sizeof(used));

    for(i = 0; i < V.size(); i++)
    {
        used[V[i]] = 1;
        if( P[V[i]].y < ymin || (P[V[i]].y == ymin && P[V[i]].x < xmin))
            xmin = P[V[i]].x, ymin = P[V[i]].y, ind = V[i];
    }
    
    for(AUX[j = 1] = ind, i = 0; i < G[ind].size(); i++)
     if(used[G[ind][i]])
        AUX[++j] = G[ind][i];

    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[i-2], AUX[i], AUX[i-1]) );
    }

    return area;
}

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

    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), k = 0; k < N; k++)
         if( cross(i, j, k) == -1 )
            V.pb(k);
        r1 = calc(V);
        for(V.clear(), V.pb(j), k = 0; k < N; k++)
         if( cross(i, j, k) == 1 )
            V.pb(k);
        r2 = calc(V);

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

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

        // +1 cu i, -1 cu j
        for(V.clear(), V.pb(j), k = 0; k < N; k++)
         if( cross(i, j, k) == -1 )
            V.pb(k);
        r1 = calc(V);
        for(V.clear(), V.pb(i), k = 0; k < N; k++)
         if( cross(i, j, k) == 1 )
            V.pb(k);
        r2 = calc(V);

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

        if(c > c2) c = c2;
        
        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;
}