Cod sursa(job #1242906)

Utilizator andreiiiiPopa Andrei andreiiii Data 15 octombrie 2014 10:50:45
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <cmath>

using namespace std;

typedef long long i64;

const int Nmax = 305;

struct Point {
    int x, y;

    Point() {}
    Point(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

Point points[Nmax];
int under[Nmax][Nmax];
i64 mina[Nmax];

inline i64 mabs(i64 n) {
    return n < 0 ? -n: n;
}

i64 det(const Point& o, const Point &a, const Point &b) {
    return 1LL * (a.x - o.x) * (b.y - o.y) - 1LL * (b.x - o.x) * (a.y - o.y);
}

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

    int N, K;
    scanf("%d%d", &N, &K);

    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", &points[i].x, &points[i].y);
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {

            Point a = points[i], b = points[j];
            if (a.x > b.x)
                swap(a, b);

            int count = 0;
            for (int k = 1; k <= N; ++k) {
                if (k == j || k == i)
                    continue;

                Point c = points[k];
                if (c.x >= a.x && c.x < b.x && det(c, a, b) < 0)
                    ++count;
            }

            under[i][j] = count;
        }
    }

    i64 ans = 1e18;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            memset(mina, 0x3f3f3f3f, sizeof mina);

            for (int k = 1; k <= N; ++k) {
                if (k == j || k == i)
                    continue;

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

                if (det(points[c], points[a], points[b]) < 0)
                    continue;

                if (points[c].x < points[a].x)
                    swap(a, c);
                if (points[b].x < points[a].x)
                    swap(a, b);
                if (points[b].x < points[c].x)
                    swap(b, c);

                int cnt = mabs(under[a][c] + under[c][b] - under[a][b]);
                i64 area = mabs(det(points[a], points[b], points[c]));
                mina[cnt] = min(mina[cnt], area);

                //assert(area > 0);
            }

            for (int i = N - 1; i >= 0; --i)
                mina[i] = min(mina[i], mina[i + 1]);

            for (int k = 1; k <= N; ++k) {
                if (k == j || k == i)
                    continue;

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

                if (det(points[c], points[a], points[b]) > 0)
                    continue;

                if (points[c].x < points[a].x)
                    swap(a, c);
                if (points[b].x < points[a].x)
                    swap(a, b);
                if (points[b].x < points[c].x)
                    swap(b, c);

                int cnt = mabs(under[a][c] + under[c][b] - under[a][b]);
                i64 area = mabs(det(points[a], points[b], points[c]));
                ans = min(ans, mina[max(0, K - cnt)] + area);

                //assert(ans > 0);
            }
        }
    }

    cout << setprecision(1) << fixed;
    cout << (double) ans / 2.0 << '\n';
}