2495875_ac_0ms_192k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 64 行

#include <math.h>
#include <stdio.h>
#include <string.h>

int n;
struct node
{
	double x, y;
}pot[13];
int map[13][13], c[13];

double dis(int i,int j)
{
	return sqrt((pot[i].x-pot[j].x)*(pot[i].x-pot[j].x)+(pot[i].y-pot[j].y)*(pot[i].y-pot[j].y));
}

int fit(int v,int num)
{
	int i, j;

	for(i = 0; i < num; i++)
	{
		c[v] = i;
		for(j = 0; j < n; j++)
		{
			if(map[v][j]&&c[j]==c[v])
				goto con;
		}
		if(v==n-1||fit(v+1,num))
			return 1;
con:
		;
	}
	return 0;
}

int main()
{
	int i, j, cas = 1;
	int max, mid, min;

	while(scanf("%d",&n)==1,n)
	{
		memset(map,0,sizeof(map));
		for(i = 0; i < n; i++)
			scanf("%lf%lf",&pot[i].x,&pot[i].y);
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++)
				if(dis(i,j)-20<=0)
					map[i][j] = map[j][i] = 1;
		min = 1;max = n;
		while(min<max)
		{
			memset(c,-1,sizeof(c));
			mid = (max+min)/2;
			if(fit(0,mid))
				max = mid;
			else
				min = mid+(min==mid);
		}
		printf("The towers in case %d can be covered in %d frequencies.\n",cas++,min);
	}
	return 1;
}