Cod sursa(job #2290849)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 27 noiembrie 2018 09:04:54
Problema Popandai Scor 24
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("popandai.in");
ofstream out("popandai.out");

const int MAXN = 300;

typedef long double ld;

int n, k;
struct Point {
	int x, y;
	bool operator<(const Point &a) {
		return x < a.x;
	}
	Point (int _x = 0, int _y = 0) {
		x = _x;
		y = _y;
	}
} p[MAXN + 1];

int under[MAXN + 1][MAXN + 1];
int dp[MAXN + 2];
int ans = 2000000000;

struct Elem {
	int arie, point, in;
	bool operator<(const Elem &a) {
		return in < a.in;
	}
	Elem (int _arie = 0, int _point = 0, int _in = 0) {
		arie = _arie;
		point = _point;
		in = _in;
	}
};

long long int det(Point a, Point b, Point c) {
	return 1LL * a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y; 
}


int main() {
	in >> n >> k;
	vector<Elem> st, dr;

	for (int i = 1; i <= n; ++ i) in >> p[i].x >> p[i].y;
	sort(p + 1, p + n + 1);

	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(p[i], p[j], p[k]) > 0)
					++ under[i][k], ++ under[k][i];

	for (int i = 1; i <= n; ++ i) {
		for (int j = i + 1; j <= n; ++ j) {
			st.clear();
			dr.clear();
			for (int k = 1; k <= n; ++ k) {
				if (k != i && k != j) {
					Elem cur;
					cur.point = k;
					cur.arie = abs(det(p[i], p[j], p[k]));
					if (det(p[i], p[j], p[k]) > 0) {
						if (k < i) cur.in = under[k][j] - under[k][i] - under[i][j];
						else if (i < k && k < j) cur.in = under[k][i] + under[k][j] - under[i][j];
						else if (j < k) cur.in = under[i][k] - under[j][k] - under[i][j];
						if (p[i].x == p[k].x || p[j].x == p[k].x) -- cur.in;
						st.push_back(cur);
					} else {
						if (k < i) cur.in = under[k][i] + under[i][j] - under[j][k];
						else if (i < k && k < j) cur.in = under[i][j] - under[i][k] - under[j][k];
						else if (j < k) cur.in = under[i][j] + under[j][k] - under[k][i];
						if (p[i].x == p[k].x || p[j].x == p[k].x) -- cur.in;
						dr.push_back(cur);
					}
				}
			}
			sort(st.begin(), st.end());
			memset(dp, 0x3f3f3f3f, sizeof(dp));
			for (auto &x : dr) dp[x.in] = min(dp[x.in], x.arie);
			for (int i = n; i >= 1; -- i) dp[i] = min(dp[i], dp[i + 1]);
			for (auto &x : st) ans = min(ans, x.arie + dp[max(k - x.in, 0)]);
		}
	}

	out << fixed << setprecision(1) << ld(ans) / 2.0;

	return 0;
}