Cod sursa(job #167391)

Utilizator raula_sanChis Raoul raula_san Data 29 martie 2008 15:47:49
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.21 kb
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>

#define maxN 301
#define maxC 60001

#define pb push_back
#define mp make_pair

#define x first
#define y second

using namespace std;

int N, K;
int Nx[maxC], Max[maxC], Nr[maxN][maxN];

vector < pair <int, int> > P;

long long R;
long long U[maxN], D[maxN];

const long long inf = ((long long) 1 << 61);

long long Mod(long long a)
{
    return
        a < 0 ? -a : a;
}

long long Area(int x0, int y0, int x1, int y1, int x2, int y2)
{
    return
        Mod((x0 * y1) + (x1 * y2) + (x2 * y0) - (y0 * x1) - (y1 * x2) - (y2 * x0)) / 2;
}

int Prod(int x0, int y0, int x1, int y1, int x2, int y2)
{
    return
        ((x2-x0) * (y1-y0)) - ((x1-x0) * (y2-y0));
}

void Swap(int &i, int &j)
{
    int t = i;
    i = j;
    j = t;
}

void ReadData()
{
    freopen("popandai.in", "rt", stdin);

    int i, x, y;
    for(scanf("%d %d", &N, &K), i=1; i<=N; ++i)
    {
        scanf("%d %d", &x, &y);
        x *= 2;

        ++ Nx[x];
        Max[x] = y > Max[x] ? y : Max[x];

        P.pb(mp(x, y));
    }

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

    fclose(stdin);
}

void PreCompute()
{
    int i, j, k;
    for(i=0; i<N; ++i)
        for(j=i+1; j<N; ++j)
        {
            for(k=0; k<N; ++k)
                if(P[k].x >= P[i].x && P[k].x <= P[j].x && Prod(P[i].x ,P[i].y, P[j].x, P[j].y, P[k].x, P[k].y) > 0)
                {
                    ++ Nr[i][j];
                    ++ Nr[j][i];
                }
        }
}

void Dynamics()
{
    int i, j, k;

    R = inf;

    for(i=0; i<=N; ++i)
        D[i] = U[i] = inf;

    for(i=0; i<N; ++i)
        for(j=i+1; j<N; ++j)
        {
            for(k=0; k<=N; ++k)
                D[k] = U[k] = inf;

            for(k=0; k<N; ++k) if(k != i && k != j)
            {
                int x0 = P[i].x, y0 = P[i].y, x1 = P[j].x, y1 = P[j].y, x2 = P[k].x, y2 = P[k].y;

                int s = Prod(x0, y0, x1, y1, x2, y2);
                long long a = Area(x0, y0, x1, y1, x2, y2);

                if(s > 0)
                {
                    if(k < i)
                    {
                        int m = Nr[i][k] + Nr[i][j] - Nr[k][j];

//                        if(Nx[x1] > 1 && Max[x1] == y1 || Nx[x2] > 1 && Max[x2] == y2) -- m;

                        if(D[m] > a) D[m] = a;
                    }
                    else if(k > j)
                    {
                        int m = Nr[i][j] + Nr[j][k] - Nr[i][k];

//                        if(Nx[x1] > 1 && Max[x1] == y1 || Nx[x2] > 1 && Max[x2] == y2) -- m;

                        if(D[m] > a) D[m] = a;
                    }
                    else
                    {
                        int m = Nr[i][j] - Nr[i][k] - Nr[k][j] - 1;

                        if(Nx[x2] > 1 && Max[x2] == y2) ++ m;

                        if(D[m] > a) D[m] = a;
                    }
                }
                else
                {
                    if(k < i)
                    {
                        int m = Nr[j][k] - Nr[k][i] - Nr[i][j] - 1;

                        if(Nx[x0] > 1 && Max[x0] == y0) ++ m;

                        if(U[m] > a) U[m] = a;
                    }
                    else if(k > j)
                    {
                        int m = Nr[i][k] - Nr[i][j] - Nr[j][k] - 1;

                        if(Nx[x1] > 1 && Max[x1] == y1) ++ m;

                        if(U[m] > a) U[m] = a;
                    }
                    else
                    {
                        int m = Nr[i][k] + Nr[k][j] - Nr[i][j];

//                        if(Nx[x1] > 1 && Max[x1] == y1 || Nx[x2] > 1 && Max[x2] == y2) -- m;

                        if(U[m] > a) U[m] = a;
                    }
                }

/*
                int a = i, b = j, c = k;

                if(x0 > x1)
                {
                    Swap(x0, x1);
                    Swap(y0, y1);
                    Swap(a, b);
                }
                if(x0 > x2)
                {
                    Swap(x0, x2);
                    Swap(y0, y2);
                    Swap(a, c);
                }
                if(x1 > x2)
                {
                    Swap(x1, x2);
                    Swap(y1, y2);
                    Swap(b, c);
                }

                int s = Prod(x0, y0, x2, y2, x1, y1);

                int ar = Area(x0, y0, x1, y1, x2, y2);

                if(s > 0)
                {
                    int m = Nr[a][c] - Nr[a][b] - Nr[b][c] - 1;

                    if(Nx[x1] > 1 && Max[x1] == y1) ++ m;

                    if(D[m] > ar) D[m] = ar;
                }
                else
                {
                    int m = Nr[a][b] + Nr[b][c] - Nr[a][c];

                    if(U[m] > ar) U[m] = ar;
                }
*/
            }

            for(k=N-1; k>=0; --k)
            {
                if(D[k+1] < D[k]) D[k] = D[k+1];
                if(U[k+1] < U[k]) U[k] = U[k+1];
            }

            for(k=0; k<=K; ++k)
                if(D[k] + U[K-k] < R) R = D[k] + U[K-k];
        }
}

void Write()
{
    freopen("popandai.out", "wt", stdout);

    if(R & 1) printf("%lld.5", R>>1);
    else
        printf("%lld.0", R>>1);

    fclose(stdout);
}

int main()
{
    ReadData();
    PreCompute();
    Dynamics();
    Write();

    return 0;
}