Cod sursa(job #6452)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 19 ianuarie 2007 17:18:01
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 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];
int 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[i].x <= A[k].x && A[k].x <= A[j].x && subd(A[i], A[j], A[k])) ||
				    (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];
//		printf("%d %d are %d puncte sub dreapta\n", i, j, sub[i][j]);
	}

	for (i = 0; i < N; ++i)
		for (j = 0; j < N; ++j)
			if (A[i].x == A[j].x && A[j].y < A[i].y)
				++cor[i];
}

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

	MS = INF << 1;

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

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

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

				if ( subd(A[t1], A[t3], A[t2]) ) {
					pct = sub[t1][t3] - sub[t1][t2] - sub[t2][t3] - 1 + cor[t2];
//					if (A[t2].x != A[t1].x && A[t2].x != A[t3].x) pct += cor[t2]; 
					under[pct] <?= arie(A[t1], A[t2], A[t3]);
//					printf("dedesupt %d %d %d are %d puncte si aria %d\n", t1, t2, t3, pct, arie(A[t1], A[t2], A[t3]));
				} else {
					pct = sub[t1][t2] + sub[t2][t3] - sub[t1][t3] - cor[t2];
//					if (A[t2].x != A[t1].x && A[t2].x != A[t3].x) pct -= cor[t2];
					over[pct] <?= arie(A[t1], A[t2], A[t3]);
//					printf("deasupra %d %d %d are %d puncte si aria %d\n", t1, t2, t3, pct, arie(A[t1], A[t2], A[t3]));
				}
			}

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

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

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

	fclose(fout);
}

int main() {
	
	read();

	process();

	minimize();

	write();

	return 0;
}