Cod sursa(job #2414754)

Utilizator osiaccrCristian Osiac osiaccr Data 24 aprilie 2019 23:31:54
Problema Popandai Scor 68
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
#define DEF 310
#define INF 1 << 29


using namespace std;

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

int n, k;

pair < int, int > V[DEF];

int sol = INF;

int sub[DEF][DEF], under[DEF], over[DEF];

int det (int i, int j, int k) {
    int delta = (V[j].first - V[i].first) * (V[k].second - V[i].second) - (V[j].second - V[i].second) * (V[k].first - V[i].first);
    return delta;
}


bool is_under (int i, int j, int k) {
    if (det (i, j, k) < 0)
        return true;
    else
        return false;
}

int nr_in_tri (int i, int j, int k) {
    if (V[i].first > V[j].first) {
        swap (i, j);
    }
    if (V[i].first > V[k].first) {
        swap (i, k);
    }
    if (V[j].first > V[k].first) {
        swap (j, k);
    }

    if (is_under (i, j, k)) { /// j sub dreapta ik
        return sub[i][j] + sub[j][k] - sub[i][k];
    }
    else {
        return sub[i][k] - sub[i][j] - sub[j][k] - 1;
    }
}

int main () {

    fin >> n >> k;

    for (int i = 1; i <= n; ++ i) {
        fin >> V[i].first >> V[i].second;
    }

    sort (V + 1, V + n + 1);

    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            for (int p = 1; p <= n; ++ p) {
                if (is_under (i, j, p) and V[i].first <= V[p].first and V[p].first <= V[j].first) {
                    ++ sub[i][j]; ++ sub[j][i];
                }
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            for (int p = 0; p <= k; ++ p) {
                over[p] = under[p] = INF;
            }

            for (int p = 1; p <= n; ++ p) {
                int nr_inside = nr_in_tri (i, j, p);
                if (is_under (i, j, p)) {
                    under[nr_inside] = min (under[nr_inside], abs (det (i, j, p)));
                }
                else {
                    over[nr_inside] = min (over[nr_inside], abs (det (i, j, p)));
                }
            }

            for (int p = k - 1; p >= 0; -- p) {
                over[p] = min (over[p], over[p + 1]);
                under[p] = min (under[p], under[p + 1]);
            }

            for (int p = 0; p <= k; ++ p) {
                if (over[p] != INF and under[k - p] != INF) {
                    sol = min (sol, over[p] + under[k - p]);
                }
            }
        }
    }

    fout << sol / 2;
    if (sol % 2 == 1) {
        fout << ".5";
    }
    else {
        fout << ".0";
    }

    return 0;
}