Cod sursa(job #1692538)

Utilizator sucureiSucureiRobert sucurei Data 21 aprilie 2016 10:00:52
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <fstream>

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

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

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 type(Point A, Point B) {
    if(A.x <= B.x)
        return 1;
    else return 2;
}

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

    return x2 < x;
}

int countPoints(int ind1, int ind2, int t) {
    int ret = 0;
    Point A = v[ind1], B = v[ind2];

    if(A.x != B.x) {
        double a, b, m, 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 i = 1; i <= N; ++i)
            if(i != ind1 && i != ind2) {
                if(v[i].y <= A.y || v[i].y >= B.y)
                    continue;
                temp1 = v[i].x, temp2 = v[i].y;
                if(isOk(v[i], m, (- b) / a))
                    ++ret;
            }
    }
    else {
        for(int i = 1; i <= N; ++i)
            if(i != ind1 && i != ind2) {
                if(v[i].y <= A.y || v[i].y >= B.y)
                    continue;
                if(v[i].x < A.x)
                    ++ret;
            }
    }

    return ret;
}

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 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, type(v[i], v[j]));

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            if(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];
            for(int k = 1; k <= N; ++k) {
                if(i == k || j == k)
                    continue;

                if(A.x != B.x) {
                    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);
                    if(type(A, B) == 1) {
                        if(isOk(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;
                        }
                    }
                    else {
                        if(isOk(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;
                        }
                    }
                }
                else {
                    if(v[k].x < A.x) {
                        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; 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;
}