Cod sursa(job #47339)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 3 aprilie 2007 16:27:39
Problema Popandai Scor 12
Compilator c Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <stdio.h>
#include <math.h>
#define NMAX 503
#define minf(a, b) (((a)-(b) < 0.000001) ? (a):(b))
#define INF 666000666

int N, K, Sub[NMAX][NMAX], X[NMAX], Y[NMAX], A, B, C;
double Arie[NMAX], Sol, S[NMAX], J[NMAX];
int PS[NMAX], PJ[NMAX];

double arie(int i, int j, int k)
{
        return  (0.5*(double)(abs(X[i]*Y[j]-X[j]*Y[i]+X[j]*Y[k]-X[k]*Y[j]+X[k]*Y[i]-X[i]*Y[k])));
}

int main()
{
        int i, j, k, a, b, c;//, si, sj, sk, sl;

        freopen("popandai.in", "r", stdin);
        scanf("%d %d", &N, &K);

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

        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]))
                {
                        k = X[i]; X[i] = X[j]; X[j] = k;
                        k = Y[i]; Y[i] = Y[j]; Y[j] = k;
                }

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                a = Y[i]-Y[j];
                b = X[j]-X[i];
                c = X[i]*Y[j]-X[j]*Y[i];
                for (k = 0; k < N; k++)
                    if ((a*X[k]+b*Y[k]+c < 0) && (X[i] <= X[k] && X[k] <= X[j]))
                       Sub[i][j]++;
                Sub[j][i] = Sub[i][j];
            }

        Sol = INF;
        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                A = Y[i]-Y[j];
                B = X[j]-X[i];
                C = X[i]*Y[j]-X[j]*Y[i];
                for (k = 0; k < N; k++) S[k] = J[k] = INF;
                for (k = 0; k < N; k++)
                {
                    a = Y[i]-Y[k];
                    b = X[k]-X[i];
                    c = X[i]*Y[k]-X[k]*Y[i];
                    if (A*X[k]+B*Y[k]+C < 0)
                    {
                       if (a*X[j]+b*Y[j]+c < 0)
                          J[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ] = minf(J[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ], arie(i, j, k));
//                          PJ[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ] = k;
                       else
                          if (a*X[j]+b*Y[j]+c > 0)
                             J[ Sub[i][j]+Sub[j][k]-Sub[i][k] ] = minf(J[ Sub[i][j]+Sub[j][k]-Sub[i][k] ], arie(i, j, k));
//                             PJ[ Sub[i][j]+Sub[j][k]-Sub[i][k] ]  = k;
                    }
                    else
                       if (A*X[k]+B*Y[k]+C > 0)
                       {
                          if (a*X[j]+b*Y[j]+c < 0)
                             S[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ] = minf(S[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ], arie(i, j, k));
//                             PS[ Sub[i][k]-Sub[i][j]-Sub[j][k]-1 ] = k;
                          else
                             if (a*X[j]+b*Y[j]+c > 0)
                                S[ Sub[i][j]+Sub[j][k]-Sub[i][k] ] = minf(S[ Sub[i][j]+Sub[j][k]-Sub[i][k] ], arie(i, j, k));
//                                PS[ Sub[i][j]+Sub[j][k]-Sub[i][k] ] = k;
                       }
                }
                for (k = 0; k <= K; k++)
                    if (J[k] < INF && S[K-k] < INF)
                       if (Sol > (J[k]+S[K-k]))
                          Sol = J[k]+S[K-k];//, si = i, sj = j, sk = PJ[k], sl = PS[K-k];
            }

        freopen("popandai.out", "w", stdout);
        printf("%.03lf\n", Sol);
        //printf("%d %d %d %d %d %d %d %d\n", X[si], Y[si], X[sj], Y[sj], X[sk], Y[sk], X[sl], Y[sl]);

        return 0;
        
}