Cod sursa(job #6585)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 20 ianuarie 2007 12:08:58
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct coor { int x, y; };

bool operator<(const coor &a, const coor &b) {
	return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

template <typename T>
T ABS(T X) { return X < 0 ? -X : X; }

const int NMAX = 324;
const int INF = 0x3f3f3f3f;

int N, K;
coor A[NMAX];
int sub[NMAX][NMAX], cor[NMAX];
unsigned MS;

void read() {
	FILE *fin = fopen("popandai.in", "rt");
	int i;

	fscanf(fin, " %d %d", &N, &K);

	for (i = 0; i < N; ++i)
		fscanf(fin, " %d %d", &A[i].x, &A[i].y);

	fclose(fin);
}

void dreapta(const coor &c1, const coor &c2, int &a, int &b, int &c) {
	a = c1.y - c2.y;
	b = c2.x - c1.x;
	c = c1.x * c2.y - c2.x * c1.y;
}

bool subd(const coor &c1, const coor &c2, const coor &c3) {
	int a, b, c;

	dreapta(c1, c2, a, b, c);

	return (a * c3.x + b * c3.y + c < 0);
}

int arie(const coor &c1, const coor &c2, const coor &c3) {
	int a, b, c;

	dreapta(c1, c2, a, b, c);

	return ABS( c3.x * a + c3.y * b + c );
}

void process() {
	int i, j, k;

	for (i = 0; i < N; ++i)
		for (j = 0; j < i; ++j) {

			for (k = 0; k < N; ++k)
				if (A[j].x <= A[k].x && A[k].x <= A[i].x && subd(A[j], A[i], A[k]))
					++sub[i][j];

			sub[j][i] = sub[i][j];
	}

	for (i = 1; i < N; ++i)
		if (A[i].x == A[i - 1].x)
				cor[i] = 1;
}

void minimize() {
	int i, j, k;
	int t1, t2, t3, pct;
	int under[NMAX], over[NMAX];

	MS = INF << 2u;

	for (i = 0; i < N; ++i)
		for (j = 0; j < i; ++j) {
			
			memset(under, 0x6f, sizeof(under));
			memset(over, 0x6f, sizeof(over));
//			under[0] = over[0] = 0;

			for (k = 0; k < N; ++k) if (i != k && j != k) {
				t1 = i; t2 = k; t3 = j;

				if (A[t2] < A[t1]) swap(t1, t2);
				if (A[t3] < A[t2]) swap(t2, t3);
				if (A[t2] < A[t1]) swap(t1, t2);

				if ( subd(A[t1], A[t3], A[t2]) )
					pct = sub[t1][t3] - sub[t1][t2] - sub[t2][t3] - 1 + cor[t2];
				else
					pct = sub[t1][t2] + sub[t2][t3] - sub[t1][t3] - cor[t2];

				if ( subd(A[j], A[i], A[k]) )
					under[pct] <?= arie(A[i], A[j], A[k]);
				else	
					over[pct] <?= arie(A[i], A[j], A[k]);
			}

			for (k = K - 1; k >= 0; --k)
				under[k] <?= under[k + 1],
				over[k] <?= over[k + 1];

			for (k = 0; k <= K; ++k)
				MS <?= (unsigned) over[k] + under[K - k];
		}
}

void write() {
	FILE *fout = fopen("popandai.out", "wt");

	fprintf(fout, "%u.%d\n", MS >> 1u, MS & 1u ? 5 : 0);

	fclose(fout);
}

int main() {
	
	read();

	sort(A, A + N);

	process();

	minimize();

	write();

	return 0;
}