Cod sursa(job #809400)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 8 noiembrie 2012 11:35:34
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int MaxN = 305;
const double oo = 1e11;

pii Points[MaxN];
int N, K, Inside[MaxN][MaxN];
double DP[2][MaxN], Sol;

inline void GetEquation(pii p1, pii p2, int &a, int &b, int &c) {
    if (p1.x == p2.x) {
        a = 1; b = 0; c = -p1.x;
    }
    else {
        a = p2.y - p1.y; b = p1.x - p2.x; c = -a*p1.x - b*p1.y;
    }
}

inline int Sign(int a, int b, int c, pii p) {
    if (a*p.x + b*p.y + c == 0)
        return 0;
    if (a*p.x + b*p.y +c < 0)
        return -1;
    return 1;
}

void Preprocess() {
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (Points[j].y < Points[i].y)
                continue;
            int a, b, c; GetEquation(Points[i], Points[j], a, b, c);
            for (int k = 1; k <= N; ++k)
                Inside[i][j] += (Sign(a, b, c, Points[k]) == -1 && Points[i].y <= Points[k].y && Points[k].y <= Points[j].y);
        }
    }
}

inline int InsideTriangle(int i, int j, int k) {
    pii T[3] = {make_pair(Points[i].y, i), make_pair(Points[j].y, j), make_pair(Points[k].y, k)};
    sort (T, T+3); i = T[0].y, j = T[1].y, k = T[2].y;
    int a, b, c; GetEquation(Points[i], Points[k], a, b, c);
    int sign = Sign(a, b, c, Points[j]);
    return  sign*Inside[i][j] + sign*Inside[j][k] - sign*Inside[i][k] - (sign == -1);
}

inline double Area(pii p1, pii p2, pii p3) {
    return 0.5*abs(p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p2.x*p1.y - p1.x*p3.y);
}

void InitDP() {
    for (int i = 0; i <= N; ++i)
        DP[0][i] = DP[1][i] = oo;
}

void BuildDP(int p1, int p2) {
    InitDP();
    int a, b, c; GetEquation(Points[p1], Points[p2], a, b, c);
    for (int i = 1; i <= N; ++i) {
        if (i == p1 || i == p2)
            continue;
        int side = Sign(a, b, c, Points[i]) == -1 ? 0 : 1;
        int inside = InsideTriangle(p1, p2, i);
        DP[side][inside] = min(DP[side][inside], Area(Points[p1], Points[p2], Points[i]));
    }
    for (int inside = N-1; inside >= 0; --inside)
        DP[0][inside] = min(DP[0][inside], DP[0][inside+1]), DP[1][inside] = min(DP[1][inside], DP[1][inside+1]);
}

void Solve() {
    Preprocess();
    Sol = oo;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j || Points[j].y < Points[i].y)
                continue;
            BuildDP(i, j);
            for (int inside = 0; inside <= K; ++inside)
                Sol = min(Sol, DP[0][inside]+DP[1][K-inside]);
        }
    }
}

void Read() {
    freopen("popandai.in", "r", stdin);
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i)
        scanf("%d %d", &Points[i].x, &Points[i].y);
}

void Print() {
    freopen("popandai.out", "w", stdout);
    printf("%.1lf\n", Sol);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}