Cod sursa(job #1253789)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 1 noiembrie 2014 19:50:57
Problema Popandai Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 305
#define INF 0x3f3f3f3f
#define infile "popandai.in"
#define outfile "popandai.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int n, K;

double Up[DIM], Down[DIM];

int Under[DIM][DIM];

struct point {
	int x;
	int y;
} v[DIM];

bool cmp(const point &a, const point &b) {
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}

int det(const point &a, const point &b, const point &c) {
	long long res = 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);
	return (int)res;
}

int main() {
	f >> n >> K;
	for (int i = 1; i <= n; ++i)
		f >> v[i].x >> v[i].y;
	
	std::sort(v + 1, v + n + 1, cmp);
	
	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(v[i], v[k], v[j]) < 0)
					++Under[i][k], ++Under[k][i];
	
	double SOL = INF;
	
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = 0; k <= n; ++k)
				Up[k] = Down[k] = INF;
			for (int k = 1; k <= n; ++k) {
				if (k == i || k == j)
					continue;
				int a = i, b = k, c = j;
				if (b < a) {
					int tmp = b;
					b = a;
					a = b;
				}
				if (b > c) {
					int tmp = b;
					b = c;
					c = b;
				}
				int nr_points = Under[a][b] + Under[b][c] - Under[a][c];
				if (nr_points < 0)
					(nr_points *= -1)--;
				if (det(v[i], v[j], v[k]) > 0)
					Up[nr_points] = std::min(det(v[i], v[j], v[k]) / 2.0, Up[nr_points]);
				else
					Down[nr_points] = std::min((-det(v[i], v[j], v[k])) / 2.0, Down[nr_points]);
			}
			for (int k = n - 1; k >= 0; --k) {
				Up[k] = std::min(Up[k + 1], Up[k]);
				Down[k] = std::min(Down[k + 1], Down[k]);
			}
			for (int k = 0; k <= K; ++k)
				SOL = std::min(SOL, Up[k] + Down[K - k]);
		}
	}
	g << setprecision(1) << fixed << SOL;
	return 0;
}

//Trust me, I'm the Doctor!