主题：求一个算法 -- 东方射日

原问题：

在大平原上有N个居民点，现要建立一个电视发射塔，试寻找发射塔的设立点，能够以最小发射功率（即最小覆盖半径）覆盖上述所有居民点。

也就是2D平面上有N个点，寻找能够包含上述所有点的最小半径的圆的圆心。

升级版：

3D空间中有N个点，寻找能够包含上述所有点的最小半径的球的球心。

理论主要看传播介质，遮蔽，地物。就是普通的电磁波传播模型。

实际上，用个测试车一跑就行了。就是画个圆。

如果只说“2D平面上有N个点，寻找能够包含上述所有点的最小半径的圆的圆心”

那多枯燥啊，小朋友还问了，为什么要找这个圆心捏？

所以啊，就和实际硬扯上点关系，表明俺的算法是有实际应用的。

事实上也是有实际应用的，比如说啊，如果不考虑树木，大建筑等阻挡物的理想情况，先敲下键盘，算出那个点，然后再用测试车到那个理论点附近跑跑找出实际点，比起毫无目的地乱跑还是可以省点油钱吧。

俺也是那么想的....

因为有一个正三角形就不行。

所有算法取决于麦克斯韦方程，从中导出的电磁波在真空中的传播模型。根据这个模型，每个地方有一个特殊传播模型。不过，这个模型最根本的因素就是接收机到发射机的距离。

所以，只要知道距离这个因素。你进行外场测试、设置基站的时候，就不会盲目了。

先前想当然，胡说八道了一通。老祖宗是怎么说的来的？闭门瞎想而不去学习是很危险滴。我往外这么一看，才知道这题目别人已经做得很细了。所以赶快销尸灭迹

简单介绍一下别人怎么做。思路：至少会有两个居民点在所要圆的圆周上。对所有居民点（或是用convex hull算法过滤后的居民点）求最远点Voronoi图。所要圆的圆心必定位于该Voronoi图的顶点或边上。这样一来，整个问题就转化为对给定点集求Voronoi图。

具体程序也有现成的，这里推荐LEDA，它是用C++写成的STD库。感兴趣的可以看下面的程序举例。有觉得能做得比LEDA好的站出来

想像一个三角形，如果我没理解错的话，你是以三边中的长边的中点作为圆心。对于钝角或直角三角形成立，对锐角三角形显然不成立。此时符合题意的点应当是外接圆的圆心。不在边上。

另外你的步骤一好像应该想寻找凸包，剔除内部点吧？如果是的话应该是正确的一步。显然有：

1.发射塔必然在凸包内

2.能覆盖凸包的顶点也必定能覆盖凸包内部的点

凸包有很多标准算法，可以自己搜索

• 还是不对

首先计算出包含所有点的一个convex hull，然后在这个convex hull上找出两个顶点，使得它们之间的距离最大。找到这两个顶点后，以这两点的中点为圆心，以顶点到中点点距离为半径，做圆。

东方射日:好像不对

这里面我说到了convex hull，应该是第一步。

那么对于只有三个点的简单情况，在锐角三角形的情况下，你所说的方法不对。

再找经过这四个偏散点最大的圆

还是要用凸包。在凸包上找出距离最远的两个点，然后求所有其它点到这两点的夹角，取夹角最小的那个点，和这两点做三角形。该三角形的“外心”（外接圆的圆心）就是你要的结果。

还是用一个三角形，如果是一个钝角三角形呢？那么外心在三角形外，简单画画就知道此时要找的点不是外心，而简单就是长边的中点。

综合一下应该是答案了吧：

1.找凸包

2.找最长连线的两点

3.凸包上其他点按与上述两点间的夹角排序

4.找到最小夹角（必然大于60，否则断言错误）

5.如果夹角小于90，取此三点外接圆圆心；否则取两点中点

有没有错误？

1.如果只有三个点呢？

2.即使有四个点，你拿北京，天津，石家庄和广州四个城市为例试试看看是不是在对角线交点上。