Cod sursa(job #164774)

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

using namespace std;

const int N_MAX = 310;
const double INF = 2000000000;

int N;
int sub[N_MAX][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 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 = 0; i <= K; i ++) over[i] = INF, under[i] = INF;

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

			A = v[i], B = v[j];
			for (int k = j + 1; k <= N; k ++) {

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

	double MIN = INF;
	for (int x = 0; x <= K; x ++) {
		if (over[x] + under[K - x] < MIN) MIN = over[x] + under[K - x];
	}

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

	return 0;
}