Cod sursa(job #508112)

Utilizator freak93Adrian Budau freak93 Data 7 decembrie 2010 16:20:32
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second

using namespace std;

const char iname[] = "popandai.in";
const char oname[] = "popandai.out";
const int maxn = 305;
const int inf = 1000000000;

ifstream f(iname);
ofstream g(oname);

int under[maxn][maxn], n, p, i, j, k, rez, half[2][maxn], zone, r; 

pair<int, int> a[maxn];

int mod(int a) {
	if (a < 0)
		return -a;
	return a;
}

int area(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

int points_inside(int p, int q, int r) {
	if (a[r] < a[p]) {
		int aux = p;
		p = r;
		r = aux;
	}
	else
		if (a[r] < a[q]) {
			int aux = q;
			q = r;
			r = aux;
		}

	return mod(under[p][q] + under[q][r] - under[p][r]) - (area(a[p], a[r], a[q]) < 0);
}

int main() {
	f >> n >> p;
	for (i = 0; i < n; ++i)
		f >> a[i].x >> a[i].y;

	sort(a, a + n);
	for (i = 0; i < n; ++i)
		for (j = i + 1; j < n; ++j)
			for (k = 0; k < n; ++k)
				if (k != i && k != j && a[i].x <= a[k].x && a[k].x < a[j].x)
					if (area(a[i], a[j], a[k]) < 0)
						++under[i][j], ++under[j][i];

	rez = inf;
	for (i = 0; i < n; ++i)
		for (j = i + 1; j < n; ++j) {
			for (k = 0; k < n; ++k)
				half[0][k] = half[1][k] = inf;
			for (k = 0; k < n; ++k)
				if (k != i && k != j) {
					zone = (int)(area(a[i], a[j], a[k]) < 0);
					r = points_inside(i, j, k);
					half[zone][r] = min(half[zone][r], mod(area(a[i], a[j], a[k])));
             }
			
            for (k = n - 2; k >= 0; --k) {
				half[0][k] = min(half[0][k], half[0][k + 1]);
				half[1][k] = min(half[1][k], half[1][k + 1]);
			}

			for(k = 0; k <= p; ++k)
				rez = min(rez, half[0][k] + half[1][p - k]);
		}
	g << rez/2 << "." << (rez % 2) * 5 << "\n";
}