Cod sursa(job #164941)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 24 martie 2008 23:06:02
Problema Popandai Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

const int N_MAX = 310;

int N;
int sub[N_MAX][N_MAX], used[N_MAX];
pair <int, int> v[N_MAX];
double over[N_MAX], under[N_MAX];

int semn(int a, int b, int c)
{
	int x = v[a].first, y = v[a].second, x1 = v[b].first, y1 = v[b].second, x2 = v[c].first, y2 = v[c].second;
	return (x * (y1 - y2) - y * (x1 - x2) + (x1 * y2) - (y1 * x2));
}

double mabs(double a)
{
	return (a < 0 ? -a : a);
}

double arie(int a, int b, int c)
{
	return (mabs(0.5 * semn(a, b, c)));
}

void preproc()
{
	for (int i = 1; i < N; i ++) {
		for (int j = i + 1; j <= N; j ++) {
			for (int k = 1; k <= N; k ++) {

				if (v[i].first <= v[k].first && v[k].first <= v[j].first && semn(k, i, j) < 0) sub[i][j] ++;
			}
		}
	}
}

int calc(int i, int j, int k)
{
	int nrpct;
	if (k <= i) {
		nrpct = sub[k][j] - sub[k][i] - sub[i][j] - 1;
		if (used[i]) nrpct ++;
		return nrpct;
	}
	if (i <= k && k <= j) {
		nrpct = sub[i][k] + sub[k][j] - sub[i][j];
		if (used[k]) nrpct --;
		return nrpct;
	}
	nrpct = sub[i][k] - sub[i][j] - sub[j][k] - 1;
	if (used[j]) nrpct ++;

	return nrpct;
}

int calc2(int i, int j, int k)
{
	int nrpct;
	if (k <= i) {
		nrpct = sub[k][i] + sub[i][j] - sub[k][j];
		if (used[i]) nrpct --;
		return nrpct;
	}
	if (i <= k && k <= j) {
		nrpct = sub[i][j] - sub[i][k] - sub[k][j] - 1;
		if (used[k]) nrpct ++;
	}
	nrpct = sub[i][j] + sub[j][k] - sub[i][k];
	if (used[j]) nrpct --;
	
	return nrpct;
}

int main()
{
	freopen("popandai.in", "r", stdin);
#ifndef _SCREEN_
	freopen("popandai.out", "w", stdout);
#endif

	int K, x, y;

	scanf("%d %d\n", &N, &K);
	for (int i = 1; i <= N; i ++) {
		scanf("%d %d\n", &x, &y);
		v[i] = make_pair(x, y);
	}

	sort(v + 1, v + N + 1);
	preproc();

	pair <int, int> A, B;
	double ar;
	int nrpct;

	for (int i = 1; i <= N; i ++) {
		for (int j = i + 1; j <= N; j ++) {
			sub[j][i] = sub[i][j];
		}
	}

	for (int i = 1; i <= N; i ++) {
		for (int j = 1; j <= N; j ++) {
			if (i != j && v[i].first == v[j].first && v[j].second < v[i].second) used[i] = 1;
		}
	}

	double MINN = -1, MIN;

	for (int i = 1; i < N - 1; i ++) {
		for (int j = i + 1; j <= N; j ++) {

			for (int k = 0; k <= N; k ++) over[k] = -1, under[k] = -1;

			for (int k = 1; k <= N; k ++) {

				if (k != i && k != j) {

					ar = arie(i, j, k);
					if (semn(k, i, j) > 0) {
						nrpct = calc(i, j, k);
						if (used[k]) nrpct --;
						if (ar < over[nrpct] || over[nrpct] == -1) over[nrpct] = ar;
					} else {
						nrpct = calc2(i, j, k);
						if (used[k]) nrpct ++;
						if (ar < under[nrpct] || under[nrpct] == -1) under[nrpct] = ar;
					}
				}
			}

			MIN = -1;
			for (int KK = K; KK <= N - 3; KK ++) {
				for (int x = 0; x <= KK; x ++) {
					if (over[x] != -1 && under[KK - x] != -1 && (over[x] + under[KK - x] < MIN || MIN == -1)) {
						MIN = over[x] + under[KK - x];
					}
				}
			}

//			printf("!!%d %d %0.1lf\n", i, j, MIN);

			if (MIN != -1 && (MIN < MINN || MINN == -1)) MINN = MIN;
		}
	}

	printf("%0.1lf\n", MINN);

	return 0;
}