Cod sursa(job #50626)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 7 aprilie 2007 23:22:36
Problema Popandai Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define NMAX 330
#define x first
#define y second
#define INF 666666
#define eps 0.0000001
#define MAX(a,b) (((a)-(b)>eps) ? (a):(b))

using namespace std;

struct pp
{
        int a, b, c;
} Pp[3];

bool operator<(const struct pp &x, const struct pp &y)
{
        return ( (x.a<y.a) || (x.a==y.a && x.b<y.b) );
}

int Under[NMAX][NMAX], N, K;
vector<pair<int,int> > P;
double Amax=INF, Up[NMAX], Down[NMAX];

int main()
{
        int i, j, k, x, y, ii, jj, kk;
        double xjos, yjos, sup;
        int x1,x2,x3,y1,y2,y3,det;

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

        for (i = 1; i <= N; i++){
            scanf("%d %d", &x, &y);
            P.push_back(make_pair(x,y)); }

        sort(P.begin(), P.end());

         for (i = 0; i < N; i++)
            for (j = i+1; j < N; j++)
            {
                x2 = P[i].x; y2 = P[i].y; x3 = P[j].x; y3 = P[j].y;
                for (k = 0; k < N; k++)
                    if ((i!=k&&j!=k)&&(P[i].x <= P[k].x && P[k].x <= P[j].x))
                    {
                        x1 = P[k].x; y1 = P[k].y; 
                        det = x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
                        Under[i][j] += (det<0);
                    }
                Under[j][i] = Under[i][j];
            }

        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
            {
                memset(Up,0,sizeof(Up));
                memset(Down,0,sizeof(Down));
                for (k = 0; k < N; k++)
                if (i != j && i != k && j != k)
                {
                        Pp[0].a = P[i].x; Pp[0].b = P[i].y; Pp[0].c = i;
                        Pp[1].a = P[j].x; Pp[1].b = P[j].y; Pp[1].c = j;
                        Pp[2].a = P[k].x; Pp[2].b = P[k].y; Pp[2].c = k;
                        sort(&Pp[0], &Pp[3]);
                        x1 = Pp[1].a; y1 = Pp[1].b; x2 = Pp[0].a; y2 = Pp[0].b; x3 = Pp[2].a; y3 = Pp[2].b;
                        ii = Pp[0].c; jj = Pp[1].c; kk = Pp[2].c;
                        det = x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
                        if ( det<0 )
                        {
                           Down[ x=Under[ii][kk]-Under[ii][jj]-Under[jj][kk] ] = MAX(0.5*abs(det),Down[ Under[ii][kk]-Under[ii][jj]-Under[jj][kk] ]);
                           if (x < 0)
                              return 1;
                        }
                        if ( det>0 )
                        {
                           Up[ x=Under[ii][jj]+Under[jj][kk]-Under[ii][kk] ] = MAX(0.5*abs(det),Up[ Under[ii][jj]+Under[jj][kk]-Under[ii][kk] ]);
                           if (x < 0)
                              return 1;
                        }
                }
                
                for (k = 0; k <= K; k++)
                    if ((Down[k]>eps && Up[K-k]>eps)&&(Amax > (Down[k]+Up[K-k])))
                       Amax = Down[k]+Up[K-k];
            }

        freopen("popandai.out", "w", stdout);
        printf("%02lf\n", Amax);

        return 0;
        
}