Pagini recente » Cod sursa (job #1446772) | Cod sursa (job #664791) | Cod sursa (job #1162790) | Cod sursa (job #1453963) | Cod sursa (job #2414759)
#include <bits/stdc++.h>
#define DEF 310
using namespace std;
ifstream fin ("popandai.in");
ofstream fout ("popandai.out");
int n, k;
pair < int, int > V[DEF];
int sol = INF;
int sub[DEF][DEF], under[DEF], over[DEF];
const int INF = numeric_limits<int>::max ();
int det (int i, int j, int k) {
int delta = (V[j].first - V[i].first) * (V[k].second - V[i].second) - (V[j].second - V[i].second) * (V[k].first - V[i].first);
return delta;
}
bool is_under (int i, int j, int k) {
if (det (i, j, k) < 0)
return true;
else
return false;
}
int nr_in_tri (int i, int j, int p) {
if (V[i].first > V[j].first) {
swap (i, j);
}
if (V[i].first > V[p].first) {
swap (i, p);
}
if (V[j].first > V[p].first) {
swap (j, p);
}
if (is_under (i, j, p)) { /// j sub dreapta ip
return sub[i][j] + sub[j][p] - sub[i][p];
}
else {
return sub[i][p] - sub[i][j] - sub[j][p] - 1;
}
}
int main () {
fin >> n >> k;
for (int i = 1; i <= n; ++ i) {
fin >> V[i].first >> V[i].second;
}
sort (V + 1, V + n + 1);
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
for (int p = 1; p <= n; ++ p) {
if (is_under (i, j, p) and V[i].first <= V[p].first and V[p].first <= V[j].first) {
++ sub[i][j]; ++ sub[j][i];
}
}
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
for (int p = 0; p <= k; ++ p) {
over[p] = under[p] = INF;
}
for (int p = 1; p <= n; ++ p) {
int nr_inside = nr_in_tri (i, j, p);
if (is_under (i, j, p)) {
under[nr_inside] = min (under[nr_inside], abs (det (i, j, p)));
}
else {
over[nr_inside] = min (over[nr_inside], abs (det (i, j, p)));
}
}
for (int p = k - 1; p >= 0; -- p) {
over[p] = min (over[p], over[p + 1]);
under[p] = min (under[p], under[p + 1]);
}
for (int p = 0; p <= k; ++ p) {
if (over[p] != INF and under[k - p] != INF) {
sol = min (sol, over[p] + under[k - p]);
}
}
}
}
fout << sol / 2;
if (sol % 2 == 1) {
fout << ".5";
}
else {
fout << ".0";
}
return 0;
}