Cod sursa(job #1832304)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 19 decembrie 2016 19:22:37
Problema Popandai Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.55 kb
#include <fstream>
#include <algorithm>
#include <complex>
#include <cstdlib>

using namespace std;

typedef complex <int> Point;

int cross(const Point &A, const Point &ref, const Point &B) {
    return (conj(A - ref) * (B - ref)).imag();
}

bool inside(const Point &A, const Point &B, const Point &C, const Point &P) {
    if (P.real() < min(A.real(), min(B.real(), C.real())))
        return false;
    if (P.real() > max(A.real(), max(B.real(), C.real())))
        return false;
    if (P.imag() < min(A.imag(), min(B.imag(), C.imag())))
        return false;
    if (P.imag() > max(A.imag(), max(B.imag(), C.imag())))
        return false;
    return abs(cross(A, P, B)) + abs(cross(B, P, C)) + abs(cross(C, P, A)) == abs(cross(A, B, C));
}

bool cmp(const Point &A, const Point &B) {
    if (A.real() != B.real())
        return A.real() < B.real();
    else
        return A.imag() < B.imag();
}

Point refer;
bool cmpAng(const Point &A, const Point &B) {
    int cc = cross(A, refer, B);
    if (cc != 0)
        return cc > 0;
    else
        return A.real() < B.real();
}

const int NMAX = 300 + 5;
const int INF = 1e9 + 15;
int N, K;
Point points[NMAX];

int dp[NMAX][NMAX];

inline int getInside(int a, int b, int c) {
    if (a > b)
        swap(a, b);
    if (a > c)
        swap(a, c);
    if (b > c)
        swap(b, c);

    int ins = dp[a][b] + dp[b][c] - dp[a][c];
    if (ins < 0)
        ins = -ins - 1;
    return ins;
}

int minAreaAbove[NMAX];
int minAreaUnder[NMAX];

int main()
{
    ifstream cin("popandai.in");
    ofstream cout("popandai.out");

    cin >> N >> K;
    for (int i = 1; i <= N; ++ i) {
        int x, y;
        cin >> x >> y;
        points[i] = Point(x, y);
    }

    int whichRefer = 1;
    for (int i = 2; i <= N; ++ i)
        if (cmp(points[i], points[whichRefer]))
            whichRefer = i;

    swap(points[whichRefer], points[1]);
    refer = points[1];
    sort(points + 2, points + N + 1, cmpAng);

    for (int i = 2; i <= N; ++ i)
        for (int j = i + 1; j <= N; ++ j)
            for (int k = 2; k <= N; ++ k)
                if (k != i && k != j)
                    dp[i][j] += inside(points[1], points[i], points[j], points[k]);

    for (int i = 0; i <= N; ++ i)
        minAreaAbove[i] = minAreaUnder[i] = INF;

    int ans = INF;
    for (int i = 1; i <= N; ++ i)
        for (int j = i + 1; j <= N; ++ j) {
            for (int k = 1; k <= N; ++ k)
                if (k != i && k != j) {
                    if (cross(points[i], points[j], points[k]) > 0) {
                        //Above
                        minAreaAbove[getInside(i, j, k)] = min(minAreaAbove[getInside(i, j, k)], +cross(points[i], points[j], points[k]));
                    }
                    else {
                        //Under
                        minAreaUnder[getInside(i, j, k)] = min(minAreaUnder[getInside(i, j, k)], -cross(points[i], points[j], points[k]));
                    }
                }

            for (int k = 0; k <= N; ++ k) {
                minAreaAbove[k] = min(minAreaAbove[k], minAreaAbove[k + 1]);
                minAreaUnder[k] = min(minAreaUnder[k], minAreaUnder[k + 1]);
            }

            for (int k = 0; k <= K; ++ k)
                ans = min(ans, minAreaAbove[k] + minAreaUnder[K - k]);

            for (int k = 0; k <= N; ++ k)
                minAreaAbove[k] = minAreaUnder[k] = INF;
        }

    if (ans & 1)
        cout << ans / 2 << ".5\n";
    else
        cout << ans / 2 << ".0\n";
    return 0;
}