大草原问题，求解答

elflyao

一片大草原上有若干人家，已知所有人家的坐标[[x1,y1],[x2,y2]......]，现在要安装若干灯，照亮所有人家，已知灯的光照半径R，求最少要多少灯

gxqcn

这个问题有点意思。

可不可以换个角度来解决这个问题：
1、以每个人家的坐标点为圆心，以R为半径画圆；
2、这些圆若有交点，将交点次数最大的点先点上灯，并将过该点或内含该点的圆依次抹去（对应的人家已获得光明）；否则转步骤4；
3、重复步骤2；
4、若所有的圆彼此相离，则在各个圆心上点灯即可。

以上是我粗略想的，是否合理、是否最佳未作探讨，故仅供参考。

sunwukong

1、做一个二维表T，初始化所有元素为0。
2、以每个人家的坐标点为圆心，以R为半径画圆；
3、判断这些圆是否有交点，有则置对应的T的元素为1。T就成为一个图的邻接矩阵。
4、问题就转化为已经一个图的邻接矩阵，把这个图划分，使得每个子图都是完全图。求最小的划分数。


不知道图论里面有没有现成的算法。