Pagini recente » Cod sursa (job #535825) | Cod sursa (job #178225) | Cod sursa (job #1027830) | Cod sursa (job #1144257) | Cod sursa (job #508112)
Cod sursa(job #508112)
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const char iname[] = "popandai.in";
const char oname[] = "popandai.out";
const int maxn = 305;
const int inf = 1000000000;
ifstream f(iname);
ofstream g(oname);
int under[maxn][maxn], n, p, i, j, k, rez, half[2][maxn], zone, r;
pair<int, int> a[maxn];
int mod(int a) {
if (a < 0)
return -a;
return a;
}
int area(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
int points_inside(int p, int q, int r) {
if (a[r] < a[p]) {
int aux = p;
p = r;
r = aux;
}
else
if (a[r] < a[q]) {
int aux = q;
q = r;
r = aux;
}
return mod(under[p][q] + under[q][r] - under[p][r]) - (area(a[p], a[r], a[q]) < 0);
}
int main() {
f >> n >> p;
for (i = 0; i < n; ++i)
f >> a[i].x >> a[i].y;
sort(a, a + n);
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
for (k = 0; k < n; ++k)
if (k != i && k != j && a[i].x <= a[k].x && a[k].x < a[j].x)
if (area(a[i], a[j], a[k]) < 0)
++under[i][j], ++under[j][i];
rez = inf;
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j) {
for (k = 0; k < n; ++k)
half[0][k] = half[1][k] = inf;
for (k = 0; k < n; ++k)
if (k != i && k != j) {
zone = (int)(area(a[i], a[j], a[k]) < 0);
r = points_inside(i, j, k);
half[zone][r] = min(half[zone][r], mod(area(a[i], a[j], a[k])));
}
for (k = n - 2; k >= 0; --k) {
half[0][k] = min(half[0][k], half[0][k + 1]);
half[1][k] = min(half[1][k], half[1][k + 1]);
}
for(k = 0; k <= p; ++k)
rez = min(rez, half[0][k] + half[1][p - k]);
}
g << rez/2 << "." << (rez % 2) * 5 << "\n";
}