Pagini recente » Cod sursa (job #2956946) | Cod sursa (job #2843563) | Cod sursa (job #2848395) | Cod sursa (job #2999077) | Cod sursa (job #2921169)
#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
typedef pair <int, int> PII;
constexpr int NMAX = 305;
ifstream f ("popandai.in");
ofstream g ("popandai.out");
int N, K;
PII A[NMAX];
int modul (int x) {
if (x < 0) x = -x;
return x;
}
int Det (PII a, PII b, PII c) {
return (c.second - a.second) * (b.first - a.first) - (c.first - a.first) * (b.second - a.second);
}
void Read () {
f >> N >> K;
for (int i = 1; i <= N; ++ i )
f >> A[i].first >> A[i].second;
sort(A+1, A+N+1);
}
int Value[NMAX][NMAX];
LD Left[NMAX], Right[NMAX];
int NumberPoints (int a, int b, int c) {
if (A[a].first > A[b].first) swap(a, b);
if (A[a].first > A[c].first) swap(a, c);
if (A[b].first > A[c].first) swap(b, c);
if (Det(A[a], A[b], A[c]) < 0)
return (Value[a][b] + Value[b][c] - Value[a][c]);
else
return (Value[a][c] - Value[a][b] - Value[b][c] - 1);
}
void Solve () {
for (int i = 1; i <= N; ++ i ) {
for (int j = i+1; j <= N; ++ j ) {
for (int k = 1; k <= N; ++ k ) {
if (A[i].first <= A[k].first && A[k].first <= A[j].first) {
if (Det(A[i], A[j], A[k]) < 0) Value[i][j] ++;
}
}
Value[j][i] = Value[i][j];
}
}
LD ans = 0;
for (int i = 1; i <= N; ++ i ) {
for (int j = i+1; j <= N; ++ j ) {
for (int k = 0; k <= N; ++ k )
Left[k] = Right[k] = 0;
for (int k = 1; k <= N; ++ k ) {
int cnt_K = NumberPoints(i, j, k);
LD area = modul(Det(A[i], A[j], A[k])) * .5;
if (Det(A[i], A[j], A[k]) < 0) {
if (Right[cnt_K] == 0)
Right[cnt_K] = area;
else Right[cnt_K] = min(Right[cnt_K], area);
}
else {
if (Left[cnt_K] == 0)
Left[cnt_K] = area;
else Left[cnt_K] = min(Left[cnt_K], area);
}
}
for (int k = 0; k <= K; ++ k ) {
if (Left[k] == 0) continue;
if (Right[K - k] == 0) continue;
if (ans == 0)
ans = Left[k] + Right[K - k];
ans = min(ans, Left[k] + Right[K - k]);
}
}
}
g << setprecision(1) << fixed << ans << '\n';
}
int main () {
Read();
Solve();
return 0;
}