Pagini recente » Cod sursa (job #3360448) | Cod sursa (job #3360447) | Cod sursa (job #3360441) | Monitorul de evaluare | Cod sursa (job #3359201)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("popandai.in");
ofstream fout("popandai.out");
const long long INF = (1LL << 60);
const int MAXN = 305;
struct Point {
long long x, y;
};
int n, k;
Point p[MAXN];
bitset<MAXN> st[MAXN][MAXN];
long long cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int cnt_triangle(int a, int b, int c) {
return (st[a][b] & st[b][c] & st[c][a]).count();
}
int main() {
fin >> n >> k;
for(int i = 0; i < n; i++) {
fin >> p[i].x >> p[i].y;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i != j) {
for(int l = 0; l < n; l++) {
if(cross(p[i], p[j], p[l]) > 0) {
st[i][j][l] = 1;
}
}
}
}
}
long long ans = INF;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
vector<long long> a(k + 1, INF), b(k + 1, INF);
for(int l = 0; l < n; l++) {
if(l == i || l == j) continue;
long long ar = llabs(cross(p[i], p[j], p[l]));
int cnt;
if(cross(p[i], p[j], p[l]) > 0) {
cnt = cnt_triangle(i, j, l);
cnt = min(cnt, k);
a[cnt] = min(a[cnt], ar);
} else {
cnt = cnt_triangle(i, l, j);
cnt = min(cnt, k);
b[cnt] = min(b[cnt], ar);
}
}
for(int l = k - 1; l >= 0; l--) {
b[l] = min(b[l], b[l + 1]);
}
for(int l = 0; l <= k; l++) {
if(a[l] == INF) continue;
int need = max(0, k - l);
if(b[need] != INF) {
ans = min(ans, a[l] + b[need]);
}
}
}
}
fout << ans / 2 << "." << (ans % 2 ? 5 : 0) << "\n";
return 0;
}