Cod sursa(job #2414762)

Utilizator osiaccrCristian Osiac osiaccr Data 24 aprilie 2019 23:42:33
Problema Popandai Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <bits/stdc++.h>
#define DEF 310

using namespace std;

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

const int INF = numeric_limits<int>::max ();

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 p) {
    if (V[i].first > V[j].first) {
        swap (i, j);
    }
    if (V[i].first > V[p].first) {
        swap (i, p);
    }
    if (V[j].first > V[p].first) {
        swap (j, p);
    }

    if (is_under (i, j, p)) { /// j sub dreapta ip
        return sub[i][j] + sub[j][p] - sub[i][p];
    }
    else {
        return sub[i][p] - sub[i][j] - sub[j][p] - 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;
}