Nu aveti permisiuni pentru a descarca fisierul grader_test5.ok

Cod sursa(job #2011353)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 15 august 2017 21:29:42
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define ll long long

#define INF 9000LL * 1000 * 1000

#define MAXN 300

int x[MAXN], y[MAXN];
ll d[2][MAXN];
int t[MAXN][MAXN];

FILE *fin = fopen("popandai.in", "r"), *fout = fopen("popandai.out", "w");

inline bool ord(int a, int b) {
    if (x[a] != x[b]) return x[a] < x[b];
    else return y[a] < y[b];
}

inline ll arie(int a, int b, int c) {
    return 1LL * x[a] * y[b] - 1LL * y[a] * x[b] + 1LL * x[b] * y[c] - 1LL * y[b] * x[c] + 1LL * x[c] * y[a] - 1LL * y[c]* x[a];
}

inline int cate(int a, int b, int c) {
    if (!ord(a, b))
        swap(a, b);
    if (!ord(b, c)) {
        swap(b, c);
        if (!ord(a, b))
            swap(a, b);
    }

    if (x[a] == x[b]) return t[b][c] - t[a][c];
    else if (x[b] == x[c]) return t[a][c] - t[a][b];
    else if (arie(a, b, c) > 0) return t[a][c] - t[a][b] - t[b][c] - 1;
    else return t[a][b] + t[b][c] - t[a][c];
}

int main() {
    int n, k;
    fscanf(fin, "%d%d", &n, &k);

    for (int i = 0; i < n; i++)
        fscanf(fin, "%d%d", &x[i], &y[i]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ord(i, j))
                for (int p = 0; p < n; p++)
                    if (arie(i, j, p) < 0 && x[i] < x[p] && x[p] < x[j])
                        t[i][j]++;

    ll ans = INF + INF;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int l = 0; l < 2; l++)
                for (int p = 0; p <= k; p++)
                    d[l][p] = INF;

            for (int p = 0; p < n; p++) if (p != i && p != j) {
                int x = min(cate(i, j, p), k);
                ll y = arie(i, j, p);
                if (y < 0) d[0][x] = min(d[0][x], -y);
                else d[1][x] = min(d[1][x], y);
            }

            for (int l = 0; l < 2; l++)
                for (int p = k - 1; p >= 0; p--)
                    d[l][p] = min(d[l][p], d[l][p + 1]);

            for (int p = 0; p <= k; p++)
                ans = min(ans, d[0][p] + d[1][k - p]);
        }
    }

    if (ans % 2) fprintf(fout, "%lld.5\n", ans / 2);
    else fprintf(fout, "%lld.0\n", ans / 2);

    fclose(fin);
    fclose(fout);
    return 0;
}