Cod sursa(job #2921169)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 27 august 2022 23:29:54
Problema Popandai Scor 76
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double LD;
typedef pair <int, int> PII;
constexpr int NMAX = 305;

ifstream f ("popandai.in");
ofstream g ("popandai.out");

int N, K;
PII A[NMAX];

int modul (int x) {
    if (x < 0) x = -x;

    return x;
}

int Det (PII a, PII b, PII c) {
    return (c.second - a.second) * (b.first - a.first) - (c.first - a.first) * (b.second - a.second);
}

void Read () {
    f >> N >> K;

    for (int i = 1; i <= N; ++ i )
        f >> A[i].first >> A[i].second;

    sort(A+1, A+N+1);
}

int Value[NMAX][NMAX];
LD Left[NMAX], Right[NMAX];

int NumberPoints (int a, int b, int c) {
    if (A[a].first > A[b].first) swap(a, b);
    if (A[a].first > A[c].first) swap(a, c);
    if (A[b].first > A[c].first) swap(b, c);

    if (Det(A[a], A[b], A[c]) < 0)
        return (Value[a][b] + Value[b][c] - Value[a][c]);
    else
        return (Value[a][c] - Value[a][b] - Value[b][c] - 1);
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = i+1; j <= N; ++ j ) {
            for (int k = 1; k <= N; ++ k ) {
                if (A[i].first <= A[k].first && A[k].first <= A[j].first) {
                    if (Det(A[i], A[j], A[k]) < 0) Value[i][j] ++;
                }
            }

            Value[j][i] = Value[i][j];
        }
    }

    LD ans = 0;

    for (int i = 1; i <= N; ++ i ) {
        for (int j = i+1; j <= N; ++ j ) {
            for (int k = 0; k <= N; ++ k )
                Left[k] = Right[k] = 0;

            for (int k = 1; k <= N; ++ k ) {
                int cnt_K = NumberPoints(i, j, k);
                LD area = modul(Det(A[i], A[j], A[k])) * .5;
                if (Det(A[i], A[j], A[k]) < 0) {
                    if (Right[cnt_K] == 0)
                        Right[cnt_K] = area;
                    else Right[cnt_K] = min(Right[cnt_K], area);
                }
                else {
                    if (Left[cnt_K] == 0)
                        Left[cnt_K] = area;
                    else Left[cnt_K] = min(Left[cnt_K], area);
                }
            }

            for (int k = 0; k <= K; ++ k ) {
                if (Left[k] == 0) continue;

                if (Right[K - k] == 0) continue;

                if (ans == 0)
                    ans = Left[k] + Right[K - k];
                ans = min(ans, Left[k] + Right[K - k]);
            }
        }
    }

    g << setprecision(1) << fixed << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}