Cod sursa(job #1039438)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 23 noiembrie 2013 00:18:36
Problema Popandai Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <fstream>

#include <cstdio>
#include <cmath>
using namespace std;

const int MAX_N = 302;
const double INF = 0x3f3f3f3f;
const double EPS = 0.001;

struct Point {
    double x, y;
};

int N, K;
int D[MAX_N][MAX_N];
double sol = INF;
double dp[2][MAX_N];
Point v[MAX_N];

inline int double_cmp(double a, double b) {
    if(a - b < -EPS)
        return -1;
    if(a - b > EPS)
        return 1;
    return 0;
}

inline bool inLeftHalfPlane(Point P, double m, double x) {
    double x1 = P.x, y1 = P.y, x2;
    x2 = x1 - y1 / m;

    return x2 < x;
}

inline double area(Point A, Point B, Point C) {
    double temp = A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - A.y * B.x - B.y * C.x;

    return abs((double) temp / 2.0);
}

int countPoints(int ind1, int ind2) {
    int ret = 0;
    double areas[5];
    Point A = v[ind1], B = v[ind2], C, D, P;

    C.x = 0, C.y = A.y;
    D.x = 0, D.y = B.y;
    areas[0] = (double) (A.x + B.x) * (B.y - A.y) / 2.0;
    for(int i = 1; i <= N; ++i)
        if(i != ind1 && i != ind2) {
            P = v[i];
            areas[1] = area(A, P, B);
            areas[2] = area(B, P, D);
            areas[3] = area(D, P, C);
            areas[4] = area(C, P, A);

            bool ok = 1;
            for(int j = 1; j <= 4; ++j)
                if(double_cmp(areas[j], 0.0) == 0)
                    ok = 0;
            if(double_cmp(areas[0], areas[1] + areas[2] + areas[3] + areas[4]) != 0)
                ok = 0;
            if(ok)
                ++ret;
        }

    return ret;
}


int main() {
    freopen("popandai.in", "r", stdin);
    freopen("popandai.out", "w", stdout);

    scanf("%d %d", &N, &K);
    for(int i = 1; i <= N; ++i)
        scanf("%lf %lf", &v[i].x, &v[i].y);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(v[i].y < v[j].y)
                D[i][j] = D[j][i] = countPoints(i, j);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            if(v[i].x >= v[j].x || v[i].y >= v[j].y)
                continue;
            for(int k = 0; k < MAX_N; ++k)
                dp[0][k] = dp[1][k] = INF;

            int r, c;
            double a, b, m, temp1, temp2;
            Point A = v[i], B = v[j];

            temp1 = A.y - B.y, temp2 = A.x - B.x;
            a = (double) temp1 / temp2;
            temp1 = A.y, temp2 = (double) a * A.x;
            b = temp1 - temp2;
            m = double (A.y - B.y) / (A.x - B.x);
            for(int k = 1; k <= N; ++k) {
                if(i == k || j == k)
                    continue;

                if(inLeftHalfPlane(v[k], m, (- b) / a)) {
                    r = 0;
                    if(v[k].y < v[i].y)
                        c = D[i][j] + D[i][k] - D[k][j];
                    else if(v[k].y < v[j].y)
                        c = D[i][j] - D[i][k] - D[k][j] - 1;
                    else c = D[i][j] + D[j][k] - D[i][k];
                }
                else {
                    r = 1;
                    if(v[k].y < v[i].y)
                        c = D[k][j] - D[i][k] - D[i][j] - 1;
                    else if(v[k].y < v[j].y)
                        c = D[i][k] + D[k][j] - D[i][j];
                    else c = D[i][k] - D[j][k] - D[i][j] - 1;
                }

                dp[r][c] = min(dp[r][c], area(v[i], v[j], v[k]));
            }

            for(int h = N - 1; h >= 0; --h)
                dp[0][h] = min(dp[0][h], dp[0][h + 1]), dp[1][h] = min(dp[1][h], dp[1][h + 1]);
            for(int h = 0; h <= K; ++h)
                sol = min(sol, dp[0][h] + dp[1][K - h]);
        }

    printf("%.1lf\n", sol);

    return 0;
}