Pagini recente » Cod sursa (job #1528676) | Cod sursa (job #988445) | Cod sursa (job #493837) | Cod sursa (job #328768) | Cod sursa (job #164774)
Cod sursa(job #164774)
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 310;
const double INF = 2000000000;
int N;
int sub[N_MAX][N_MAX];
pair <int, int> v[N_MAX];
double over[N_MAX], under[N_MAX];
int semn(int a, int b, int c)
{
int x = v[a].first, y = v[a].second, x1 = v[b].first, y1 = v[b].second, x2 = v[c].first, y2 = v[c].second;
return (x * (y1 - y2) - y * (x1 - x2) + (x1 * y2) - (y1 * x2));
}
double mabs(double a)
{
return (a < 0 ? -a : a);
}
double arie(int a, int b, int c)
{
return (mabs(0.5 * semn(a, b, c)));
}
void preproc()
{
for (int i = 1; i < N; i ++) {
for (int j = i + 1; j <= N; j ++) {
for (int k = 1; k <= N; k ++) {
if (v[i].first <= v[k].first && v[k].first <= v[j].first && semn(k, i, j) < 0) sub[i][j] ++;
}
}
}
}
int main()
{
freopen("popandai.in", "r", stdin);
#ifndef _SCREEN_
freopen("popandai.out", "w", stdout);
#endif
int K, x, y;
scanf("%d %d\n", &N, &K);
for (int i = 1; i <= N; i ++) {
scanf("%d %d\n", &x, &y);
v[i] = make_pair(x, y);
}
sort(v + 1, v + N + 1);
preproc();
pair <int, int> A, B;
double ar;
int nrpct;
for (int i = 0; i <= K; i ++) over[i] = INF, under[i] = INF;
for (int i = 1; i < N - 1; i ++) {
for (int j = i + 1; j < N; j ++) {
A = v[i], B = v[j];
for (int k = j + 1; k <= N; k ++) {
ar = arie(i, j, k);
if (semn(k, i, j) > 0) {
nrpct = sub[i][j] + sub[j][k] - sub[i][k];
if (ar < over[nrpct]) over[nrpct] = ar;
} else {
nrpct = sub[i][k] - sub[i][j] - sub[j][k];
if (ar < under[nrpct]) under[nrpct] = ar;
}
}
}
}
double MIN = INF;
for (int x = 0; x <= K; x ++) {
if (over[x] + under[K - x] < MIN) MIN = over[x] + under[K - x];
}
printf("%0.1lf\n", MIN);
return 0;
}