Cod sursa(job #88827)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 4 octombrie 2007 12:21:05
Problema Popandai Scor 16
Compilator c Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <stdio.h>
#define NMAX 333
#define INF 666000666
#define eps 1e-7

struct point
{
        int x, y;
} P[NMAX];

int N, K;
double Du[NMAX], Dd[NMAX], Area = INF;

double area(int a, int b, int c)
{
        int x1 = P[a].x, x2 = P[b].x, x3 = P[c].x;
        int y1 = P[a].y, y2 = P[b].y, y3 = P[c].y;
        int s = x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3;
        return (abs(s)*0.5);
}

int in_(int a, int b, int c, int t)
{
        int x1 = P[t].x, x2 = P[b].x, x3 = P[c].x;
        int y1 = P[t].y, y2 = P[b].y, y3 = P[c].y;
        int a1 = abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)*0.5;
        x1 = P[a].x, y1 = P[a].y;
        x2 = P[t].x, y2 = P[t].y;
        int a2 = abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)*0.5;
        x2 = P[b].x, y2 = P[b].y;
        x3 = P[t].x, y3 = P[t].y;
        int a3 = abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)*0.5;
        x1 = P[a].x, y1 = P[a].y; x3 = P[c].x; y3 = P[c].y;
        int ar = abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)*0.5;

        if (a1!=0&&a2!=0&&a3!=0)
           if (a1+a2+a3==ar) return 1;
        return 0;
}

int main()
{
        int i, j, k, t, num, rez;
        int x1, x2, x3, y1, y2, y3;
        double a;

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

        for (i = 0; i < N; i++) scanf("%d%d", &P[i].x, &P[i].y);

        for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                for (k = 0; k < N; k++) Du[k] = Dd[k] = INF;
                for (k = 0; k < N; k++)
                if (k!=j&&k!=i)
                {
                    for (t = num = 0; t < N; t++)
                    if (t!=i&&t!=j&&t!=k)
                    {
                        a = area(i,j,k)-area(i,j,t)-area(i,k,t)-area(j,k,t);
                        num += (a==0);
                    }
                    a = area(i,j,k);
                    x1 = P[k].x; x2 = P[i].x; x3 = P[j].x;
                    y1 = P[k].y; y2 = P[i].y; y3 = P[j].y;
                    rez=(x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-x1*y3);
                    if (rez < -eps)
                        if ((a-Dd[num])<eps) Dd[num] = a;
                    if (rez > -eps)
                        if ((a-Du[num])<eps) Du[num] = a;
                }
                for (k = 0; k <= K; k++)
                    if (Du[k]+Dd[K-k]<INF)
                       if ( (Du[k]+Dd[K-k]-Area) < eps)
                          Area = Du[k]+Dd[K-k];
            }
            
        freopen("popandai.out", "w", stdout);
        printf("%lf\n", Area);
        return 0;
}