Cod sursa(job #4482)

Utilizator diaDiana Adrisor dia Data 4 ianuarie 2007 09:20:16
Problema Popandai Scor 32
Compilator c Status done
Runda Arhiva de probleme Marime 3.91 kb
#include <stdio.h>
#include <math.h>
#define NMAX 303
#define minf(a, b) (((a)-(b) < 0.0001) ? (a):(b))
#define INF 666666

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, pi, pj, pk, 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++)
                {
                    pi = i; pj = j; pk = k;
                    if (X[i] == X[j] && Y[i] < Y[j]) pi = j, pj = i;
                    if (X[k] < X[i] || (X[k] == X[i] && X[k] > X[i])) pi = k, pj = i, pk = j;
                    else
                        if (X[i] < X[k])
                           if (X[k] < X[j] || (X[k] == X[j] && Y[k] < Y[j])) pi = i, pj = k, pk = j;
                    a = Y[pi]-Y[pk];
                    b = X[pk]-X[pi];
                    c = X[pi]*Y[pk]-X[pk]*Y[pi];
                    if (A*X[k]+B*Y[k]+C < 0)
                    {
                       if (a*X[pj]+b*Y[pj]+c < 0)
                          J[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ] = minf(J[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ], arie(i, j, k)),
                          PJ[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ] = k;
                       else
                          if (a*X[pj]+b*Y[pj]+c > 0)
                             J[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ] = minf(J[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ], arie(i, j, k)),
                             PJ[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ]  = k;
                    }
                    else
                       if (A*X[k]+B*Y[k]+C > 0)
                       {
                          if (a*X[pj]+b*Y[pj]+c < 0)
                             S[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ] = minf(S[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ], arie(i, j, k)),
                             PS[ Sub[pi][pk]-Sub[pi][pj]-Sub[pj][pk]-1 ] = k;
                          else
                             if (a*X[pj]+b*Y[pj]+c > 0)
                                S[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ] = minf(S[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ], arie(i, j, k)),
                                PS[ Sub[pi][pj]+Sub[pj][pk]-Sub[pi][pk] ] = 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("%.01lf\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;
        
}