Pagini recente » Cod sursa (job #1372476) | Cod sursa (job #395738) | Cod sursa (job #1050247) | Cod sursa (job #370965) | Cod sursa (job #998725)
Cod sursa(job #998725)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int MAX = 305;
const double INF = 1e12;
typedef pair<int, int> PII;
#define x first
#define y second
int N, K, B[MAX][MAX];
double ans = INF, minArea[MAX];
PII V[MAX];
void citire() {
ifstream in("popandai.in");
in >> N >> K;
for(int i = 1; i <= N; i++) {
in >> V[i].x >> V[i].y;
} in.close();
}
inline int abs(int A) {
if(A < 0) return -1 * A;
return A;
}
inline int getDeterminant(const PII &A, const PII &B, const PII &C) {
return A.x * B.y + A.y * C.x + B.x * C.y - B.y * C.x - A.y * B.x - A.x * C.y;
}
int getNumberPointsBelow(const int &i, const int &j) {
int cnt = 0;
for(int k = i + 1; k < j; k++) {
if(getDeterminant(V[i], V[j], V[k]) < 0)
cnt++;
} return cnt;
}
inline int getTrianglePoints(int i, int j, int k) {
if(i > j) swap(i, j);
if(i > k) swap(i, k);
if(j > k) swap(j, k);
if(getDeterminant(V[i], V[k], V[j]) < 0)
return B[i][k] - B[i][j] - B[j][k] - 1;
return B[i][j] + B[j][k] - B[i][k];
}
void solve() {
sort(V + 1, V + N + 1);
for(int i = 1; i < N; i++)
for(int j = i + 1; j <= N; j++)
B[i][j] = getNumberPointsBelow(i, j);
for(int i = 1; i < N; i++)
for(int j = i + 1; j <= N; j++) {
for(int k = 0; k <= N + 1; k++)
minArea[k] = INF;
for(int k = 1, cnt; k <= N; k++) {
if(k == i || k == j || getDeterminant(V[i], V[j], V[k]) >= 0) continue;
minArea[ cnt = getTrianglePoints(i, j, k) ] = min(minArea[cnt], 0.5 * abs(getDeterminant(V[i], V[j], V[k])));
}
for(int k = N; k >= 0; k--) minArea[k] = min(minArea[k], minArea[k + 1]);
for(int k = 1, cnt; k <= N; k++) {
if(k == i || k == j || getDeterminant(V[i], V[j], V[k]) < 0) continue;
cnt = max(0, K - getTrianglePoints(i, j, k));
ans = min(ans, minArea[cnt] + 0.5 * getDeterminant(V[i], V[j], V[k]));
}
}
}
void afisare() {
ofstream out("popandai.out");
out << fixed << setprecision(1) << ans << "\n";
out.close();
}
int main() {
citire();
solve();
afisare();
return 0;
}