Cod sursa(job #3359201)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 iunie 2026 02:55:11
Problema Popandai Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("popandai.in");
ofstream fout("popandai.out");

const long long INF = (1LL << 60);
const int MAXN = 305;

struct Point {
    long long x, y;
};

int n, k;
Point p[MAXN];
bitset<MAXN> st[MAXN][MAXN];

long long cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int cnt_triangle(int a, int b, int c) {
    return (st[a][b] & st[b][c] & st[c][a]).count();
}

int main() {
    fin >> n >> k;

    for(int i = 0; i < n; i++) {
        fin >> p[i].x >> p[i].y;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                for(int l = 0; l < n; l++) {
                    if(cross(p[i], p[j], p[l]) > 0) {
                        st[i][j][l] = 1;
                    }
                }
            }
        }
    }

    long long ans = INF;

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            vector<long long> a(k + 1, INF), b(k + 1, INF);

            for(int l = 0; l < n; l++) {
                if(l == i || l == j) continue;

                long long ar = llabs(cross(p[i], p[j], p[l]));
                int cnt;

                if(cross(p[i], p[j], p[l]) > 0) {
                    cnt = cnt_triangle(i, j, l);
                    cnt = min(cnt, k);
                    a[cnt] = min(a[cnt], ar);
                } else {
                    cnt = cnt_triangle(i, l, j);
                    cnt = min(cnt, k);
                    b[cnt] = min(b[cnt], ar);
                }
            }

            for(int l = k - 1; l >= 0; l--) {
                b[l] = min(b[l], b[l + 1]);
            }

            for(int l = 0; l <= k; l++) {
                if(a[l] == INF) continue;

                int need = max(0, k - l);

                if(b[need] != INF) {
                    ans = min(ans, a[l] + b[need]);
                }
            }
        }
    }

    fout << ans / 2 << "." << (ans % 2 ? 5 : 0) << "\n";

    return 0;
}