UVa 11008 - Antimatter Ray Clearcutting

// UVa 11008 - Antimatter Ray Clearcutting

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

struct point {
	int x, y;
};

int n, m, oo;
int T[65536];
point tree[16];

int cross(point p0, point p1, point p2) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

int dp(int mask, int cut) {
	if (cut >= m)
		return 0;
	if (T[mask] == oo) {
		int best_sub = oo;
		for (int i = 0; i < n; i++)
			if ((mask >> i) & 1) {
				int new_mask = mask ^ (1 << i);
				best_sub = min(best_sub, dp(new_mask, cut + 1));
				for (int j = i + 1; j < n; j++) {
					if ((mask >> j) & 1) {
						new_mask = mask ^ (1 << i) ^ (1 << j);
						int new_cut = cut + 2;
						for (int k = j + 1; k < n; k++)
							if (((mask >> k) & 1) && (cross(tree[i], tree[j], tree[k]) == 0)) {
								new_mask = new_mask ^ (1 << k);
								new_cut++;
							}
						best_sub = min(best_sub, dp(new_mask, new_cut));
					}
				}
			}
		T[mask] = best_sub + 1;
	}
	return T[mask];
}

int main() {
	int power[17];
	power[0] = 1;
	for (int i = 1; i < 17; i++)
		power[i] = power[i - 1] << 1;
	int tt;
	cin >> tt;
	for (int t = 1; t <= tt; t++) {
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> tree[i].x >> tree[i].y;
		// dp
		memset(T, 127, sizeof(T));
		oo = T[0];
		int sol = dp(power[n] - 1, 0);
		// output
		printf("Case #%d:\n%d\n", t, sol);
		if (t < tt)
			printf("\n");
	}
	return 0;
}