1266.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1266 on 2006-01-28 at 18:43:59 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const double eps = 1e-3;
const int MAX = 32;

bool near[MAX][MAX];
int clr[MAX], cn, n;

int color(int, int);

int main()
{
	int i, j, t;
	double x[MAX], y[MAX];
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		memset(near, false, sizeof(near));
		for(i = 0; i < n; i++) scanf("%lf %lf", &x[i], &y[i]);
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++)
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) < 400+eps)
					near[i][j] = near[j][i] = true;
		cn = MAX; memset(clr, -1, sizeof(clr));
		printf("The towers in case %d can be covered in %d frequencies.\n", t, color(0, 0));
	}
	
	return 0;
}

int color(int b, int total)
{
	if(b == n) cn = min(cn, total);
	else {
		int i, j;
		for(i = 0; i <= total; i++) {
			bool can = true;
			for(j = 0; j < n && i != total; j++)
				if(near[b][j] && clr[j] == i) { can = false; break; }
			int cln = (i == total) ? total+1 : total;
			if(can && cln < cn) {
				clr[b] = i; color(b+1, cln); clr[b] = -1;
			}
		}
	}
	
	return cn;
}