Nu aveti permisiuni pentru a descarca fisierul grader_test5.ok
Cod sursa(job #2011353)
Utilizator | 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;
}