Pagini recente » Cod sursa (job #3186965) | Cod sursa (job #2966535) | Cod sursa (job #918633) | Cod sursa (job #1106404) | Cod sursa (job #1253789)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 305
#define INF 0x3f3f3f3f
#define infile "popandai.in"
#define outfile "popandai.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int n, K;
double Up[DIM], Down[DIM];
int Under[DIM][DIM];
struct point {
int x;
int y;
} v[DIM];
bool cmp(const point &a, const point &b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
int det(const point &a, const point &b, const point &c) {
long long res = 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);
return (int)res;
}
int main() {
f >> n >> K;
for (int i = 1; i <= n; ++i)
f >> v[i].x >> v[i].y;
std::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(v[i], v[k], v[j]) < 0)
++Under[i][k], ++Under[k][i];
double SOL = INF;
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 0; k <= n; ++k)
Up[k] = Down[k] = INF;
for (int k = 1; k <= n; ++k) {
if (k == i || k == j)
continue;
int a = i, b = k, c = j;
if (b < a) {
int tmp = b;
b = a;
a = b;
}
if (b > c) {
int tmp = b;
b = c;
c = b;
}
int nr_points = Under[a][b] + Under[b][c] - Under[a][c];
if (nr_points < 0)
(nr_points *= -1)--;
if (det(v[i], v[j], v[k]) > 0)
Up[nr_points] = std::min(det(v[i], v[j], v[k]) / 2.0, Up[nr_points]);
else
Down[nr_points] = std::min((-det(v[i], v[j], v[k])) / 2.0, Down[nr_points]);
}
for (int k = n - 1; k >= 0; --k) {
Up[k] = std::min(Up[k + 1], Up[k]);
Down[k] = std::min(Down[k + 1], Down[k]);
}
for (int k = 0; k <= K; ++k)
SOL = std::min(SOL, Up[k] + Down[K - k]);
}
}
g << setprecision(1) << fixed << SOL;
return 0;
}
//Trust me, I'm the Doctor!