Cod sursa(job #88962)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 23:27:16
Problema Popandai Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.52 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NMAX 333
#define ABS(x) (((x)>=0)?(x):-(x))
#define MIN(a,b) (((a)<(b))?(a):(b))

int X[NMAX], Y[NMAX], A[NMAX][NMAX];
int N, K, v[4][2], Sub[NMAX], Dea[NMAX], T[NMAX][NMAX], V[NMAX][NMAX];
long long U[NMAX], Area, Up[NMAX], Down[NMAX], INF;

void read()
{
        int i;
        
        freopen("popandai.in","r",stdin);
        scanf("%d%d",&N,&K);

        for (i = 0; i < N; i++)
            scanf("%d %d", &X[i], &Y[i]);
}

long long cross(int ii, int jj, int kk)
{
        int x1 = X[ii], x2 = X[jj], x3 = X[kk];
        int y1 = Y[ii], y2 = Y[jj], y3 = Y[kk];
        return x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3;
}

void proc()
{
        int i, j, k, val;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                if ( (X[i]>X[j])||(X[i]==X[j]&&Y[i]>Y[j]) )
                   val = X[i], X[i] = X[j], X[j] = val,
                   val = Y[i], Y[i] = Y[j], Y[j] = val;

        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                if (X[i]==X[j] && Y[i]>Y[j]) T[i][ Sub[i]++ ] = j;
                if (X[i]==X[j] && Y[i]<Y[j]) V[i][ Dea[i]++ ] = j;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                for (k = i+1; k < j; k++)
                    if (cross(i,j,k)<0) A[i][j]++;

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                if (!A[i][j]) A[i][j] = A[j][i];

}

void sortv(int i, int j, int k)
{
        int t, u, z, val;

        v[0][0] = X[i]; v[1][0] = X[j]; v[2][0] = X[k];
        v[0][1] = i; v[1][1] = j; v[2][1] = k;

        for (t = 0; t < 3; t++)
            for (u = t+1; u < 3; u++)
                if (v[t][0]>v[u][0])
                   for (z = 0; z < 2; z++)
                       val = v[t][z], v[t][z] = v[u][z], v[u][z] = val;
}

void solve()
{
        int i, j, k, ii, jj, kk, np;
        int x1, x2, x3, y1, y2, y3;
        long long rez, area, a = 666000666, b = 100000, c = 666;

        proc();
        INF = a*b+c; Area = INF;
        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                for (k = 0; k < NMAX; k++) Down[k] = Up[k] = INF;
                for (k = 0; k < N; k++)
                    if (i!=k&&j!=k)
                    {
                        sortv(i, j, k);

                        ii = v[0][1]; jj = v[1][1]; kk = v[2][1];
                        area = cross(ii,jj,kk);
                        if (area>0)
                           np = A[ii][kk]-A[ii][jj]-A[jj][kk]-1;
                        else
                           np = A[ii][jj]+A[jj][kk]-A[ii][kk];
                           
                        rez = cross(i,j,k);
                        if (rez>0) Up[np] = MIN(Up[np], ABS(area));
                        else Down[np] = MIN(Down[np], ABS(area));
                    }
                for (k = N-1; k >= 0; k--)
                {
                        Up[k] = MIN(Up[k],Up[k+1]);
                        Down[k] = MIN(Down[k],Down[k+1]);
                }
                for (k = 0; k <= K; k++)
                {
                    if ((Up[k]+Down[K-k])<INF)
                       if ( (Up[k]+Down[K-k]-Area) < 0 ) Area = Up[k]+Down[K-k];
                }
             }
}

void write()
{
        freopen("popandai.out", "w", stdout);
        printf("%lf\n", (double)(Area*0.5));
}
int main()
{
        read();
        solve();
        write();
        return 0;
}