Pagini recente » Cod sursa (job #1320144) | Cod sursa (job #960017) | Cod sursa (job #1762400) | Arhiva de probleme | Cod sursa (job #2132389)
#include <cstdio>
#include <algorithm>
using namespace std;
struct Punct {
int x, y;
bool operator < (const Punct& other) const {
if (x == other.x)
return y < other.y;
return x < other.x;
}
}v[305];
int r[5];
int p[5][305][305];
int myAbs(int x) {
return x < 0 ? -x : x;
}
int area(Punct a, Punct b, Punct c) {
int ans(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
return ans;
}
int sens(Punct a, Punct b, Punct c) {
int ans = area(a, b, c);
return ans > 0;
}
int in(int i, int j, int k) {
r[1] = i;
r[2] = j;
r[3] = k;
sort(r + 1, r + 4);
i = r[1];
j = r[3];
k = r[2];
int s = sens(v[i], v[j], v[k]) ^ 1;
int ans = p[s][i][k] - p[s][i][j] - p[s][j][k];
return ans > 0 ? ans : -ans;
}
int mina[5][305];
int main() {
freopen("popandai.in", "r", stdin);
freopen("popandai.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
for (int k = i + 1; k < j; ++k)
p[sens(v[i], v[j], v[k])][i][j]++;
int ans = 1000000000;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j) {
for (int x = 0; x <= n; ++x)
mina[0][x] = mina[1][x] = 1000000000;
for (int k = 1; k <= n; ++k)
if (k != i && k != j)
mina[sens(v[i], v[j], v[k])][in(i, j, k)] = min(mina[sens(v[i], v[j], v[k])][in(i, j, k)], myAbs(area(v[i], v[j], v[k])));
for (int k = n - 1; k >= 0; --k) {
mina[0][k] = min(mina[0][k + 1], mina[0][k]);
mina[1][k] = min(mina[1][k + 1], mina[1][k]);
}
for (int k = 0; k <= m; ++k)
ans = min(ans, mina[0][k] + mina[1][m - k]);
}
printf("%.1f\n", 1. * ans / 2);
return 0;
}