Cod sursa(job #1165937)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 aprilie 2014 01:18:32
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.46 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;
}