Cod sursa(job #3267998)

Utilizator amunnumeVlad Patrascu amunnume Data 13 ianuarie 2025 13:49:28
Problema Popandai Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#define inf 1000000000;
using namespace std;

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

int n, p, i, j, k, sol;
double up[310], dn[310];
int d[310][310];
int a, b, c;
double arie;

struct Andrei {
    int x, y;
}v[310];

bool cmp(const Andrei &a, const Andrei &b) {
    return (a.x != b.x ? a.x < b.x : a.y < b.y);
}

int det(int i, int j, int k) {
    return (long long)(v[j].x - v[i].x) * (v[k].y - v[i].y) - (long long)(v[k].x - v[i].x) * (v[j].y - v[i].y);
}

int main() {
    fin >> n >> p;
    for(int i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp);

    for(int i = 1; i < n; i++)
        for(int j = i + 1; j < n; j++)
            for(int k = j + 1; k <= n; k++)
                if(det(i, k, j) < 0) {
                    d[i][k]++;
                    //d[k][i]++;
                }

    arie = inf;

    for(int i = 1; i < n; i++)
        for(int j = i + 1; j <= n; j++) {
            for(int k = 0; k <= n; k++)
                up[k] = dn[k] = inf;
            for(int k = 1; k <= n; k++) {
                if(i == k || j == k)
                    continue;
                a = min(min(i, j), k);
                c = max(max(i, j), k);
                b = i;

                if(b == a || b == c) {
                    b = j;
                    if(b == a || b == c)
                        b = k;
                }

                sol = d[a][b] + d[b][c] - d[a][c];
                if(sol < 0)
                   sol = -sol - 1;
                if(det(i, j, k) > 0)
                    up[sol] = min(up[sol], (double)det(i, j, k) / 2.0);
                else dn[sol] = min(dn[sol], -1.0 * det(i, j, k) / 2.0);
            }

            for(int k = n - 1; k >= 0; k--) {
                up[k] = min(up[k], up[k + 1]);
                dn[k] = min(dn[k], dn[k + 1]);
            }

            for(int k = 0; k <= p; k++)
                arie = min(arie, up[k] + dn[p - k]);
        }

    fout << setprecision(1) << fixed << arie << "\n";
    return 0;
}