Pagini recente » Cod sursa (job #1469305) | Cod sursa (job #2160157) | Cod sursa (job #387255) | Cod sursa (job #1455582) | Cod sursa (job #3267998)
#include <algorithm>
#include <fstream>
#include <iomanip>
#define inf 1000000000;
using namespace std;
ifstream fin("popandai.in");
ofstream fout("popandai.out");
int n, p, i, j, k, sol;
double up[310], dn[310];
int d[310][310];
int a, b, c;
double arie;
struct Andrei {
int x, y;
}v[310];
bool cmp(const Andrei &a, const Andrei &b) {
return (a.x != b.x ? a.x < b.x : a.y < b.y);
}
int det(int i, int j, int k) {
return (long long)(v[j].x - v[i].x) * (v[k].y - v[i].y) - (long long)(v[k].x - v[i].x) * (v[j].y - v[i].y);
}
int main() {
fin >> n >> p;
for(int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i < n; i++)
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k <= n; k++)
if(det(i, k, j) < 0) {
d[i][k]++;
//d[k][i]++;
}
arie = inf;
for(int i = 1; i < n; i++)
for(int j = i + 1; j <= n; j++) {
for(int k = 0; k <= n; k++)
up[k] = dn[k] = inf;
for(int k = 1; k <= n; k++) {
if(i == k || j == k)
continue;
a = min(min(i, j), k);
c = max(max(i, j), k);
b = i;
if(b == a || b == c) {
b = j;
if(b == a || b == c)
b = k;
}
sol = d[a][b] + d[b][c] - d[a][c];
if(sol < 0)
sol = -sol - 1;
if(det(i, j, k) > 0)
up[sol] = min(up[sol], (double)det(i, j, k) / 2.0);
else dn[sol] = min(dn[sol], -1.0 * det(i, j, k) / 2.0);
}
for(int k = n - 1; k >= 0; k--) {
up[k] = min(up[k], up[k + 1]);
dn[k] = min(dn[k], dn[k + 1]);
}
for(int k = 0; k <= p; k++)
arie = min(arie, up[k] + dn[p - k]);
}
fout << setprecision(1) << fixed << arie << "\n";
return 0;
}