Cod sursa(job #4633)

Utilizator diaDiana Adrisor dia Data 5 ianuarie 2007 22:37:47
Problema Popandai Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.41 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, X[NMAX], Y[NMAX];
double Arie;

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 In(int i, int j, int k, int t)
{
        int a, b, c;

        a = Y[i]-Y[k];
        b = X[k]-X[i];
        c = X[i]*Y[k]-X[k]*Y[i];

        if (a*X[j]+b*Y[j]+c > 0)
        {
                a = Y[i]-Y[j];
                b = X[j]-X[i];
                c = X[i]*Y[j]-X[j]*Y[i];
                if (a*X[t]+b*Y[t]+c > 0) return 0;
                a = Y[j]-Y[k];
                b = X[k]-X[j];
                c = X[j]*Y[k]-X[k]*Y[j];
                if (a*X[t]+b*Y[t]+c > 0) return 0;
                a = Y[i]-Y[k];
                b = X[k]-X[i];
                c = X[i]*Y[k]-X[k]*Y[i];
                if (a*X[t]+b*Y[t]+c < 0) return 0;
                return 1;
        }
        if (a*X[j]+b*Y[j]+c < 0)
        {
                a = Y[i]-Y[j];
                b = X[j]-X[i];
                c = X[i]*Y[j]-X[j]*Y[i];
                if (a*X[t]+b*Y[t]+c < 0) return 0;
                a = Y[j]-Y[k];
                b = X[k]-X[j];
                c = X[j]*Y[k]-X[k]*Y[j];
                if (a*X[t]+b*Y[t]+c < 0) return 0;
                a = Y[i]-Y[k];
                b = X[k]-X[i];
                c = X[i]*Y[k]-X[k]*Y[i];
                if (a*X[t]+b*Y[t]+c > 0) return 0;
                return 1;
        }
}

int main()
{
        int i, j, k, l, m, ii, jj, kk, ll, num = 0, si, sj, sk, sl, a, b, c, smn;

        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;
                }

        Arie = INF;
        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
                for (k = j+1; k < N; k++)
                    for (l = k+1; l < N; l++)
                    {
                        num = 0;
                        ii = i;
                        jj = j;
                        a = Y[j]-Y[k];
                        b = X[k]-X[j];
                        c = X[j]*Y[k]-X[k]*Y[j];
                        smn = (Y[j] > Y[k] ? -1:1);
                        if (smn*(a*X[l]+b*Y[l]+c) > 0)
                           kk = k, ll = l;
                        else kk = l, ll = k;
                        for (m = 0; m < N; m++)
                            if (m != i && m != k && m != l && m != j)
                               num = num+In(ii, jj, kk, m)+In(ii, kk, ll, m);
                        if (num == K)
                        {
                           if (Arie > (arie(ii, jj, kk)+arie(ii, kk, ll)))
                              Arie = arie(ii, jj, kk)+arie(ii, kk, ll), si = ii, sj = jj, sk = kk, sl = ll;
                        }
                    }

        freopen("popandai.out", "w", stdout);
        printf("%.1lf\n", Arie);
//        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;
        
}