主题：求一个算法 -- 东方射日
原问题：
在大平原上有N个居民点，现要建立一个电视发射塔，试寻找发射塔的设立点，能够以最小发射功率（即最小覆盖半径）覆盖上述所有居民点。
也就是2D平面上有N个点，寻找能够包含上述所有点的最小半径的圆的圆心。
升级版：
3D空间中有N个点，寻找能够包含上述所有点的最小半径的球的球心。
理论主要看传播介质，遮蔽，地物。就是普通的电磁波传播模型。
实际上，用个测试车一跑就行了。就是画个圆。
如果只说“2D平面上有N个点，寻找能够包含上述所有点的最小半径的圆的圆心”
那多枯燥啊，小朋友还问了，为什么要找这个圆心捏？
所以啊，就和实际硬扯上点关系，表明俺的算法是有实际应用的。
事实上也是有实际应用的，比如说啊，如果不考虑树木，大建筑等阻挡物的理想情况，先敲下键盘，算出那个点，然后再用测试车到那个理论点附近跑跑找出实际点，比起毫无目的地乱跑还是可以省点油钱吧。
俺也是那么想的....
因为有一个正三角形就不行。
所有算法取决于麦克斯韦方程，从中导出的电磁波在真空中的传播模型。根据这个模型，每个地方有一个特殊传播模型。不过，这个模型最根本的因素就是接收机到发射机的距离。
所以，只要知道距离这个因素。你进行外场测试、设置基站的时候，就不会盲目了。
先前想当然，胡说八道了一通。老祖宗是怎么说的来的？闭门瞎想而不去学习是很危险滴。我往外这么一看，才知道这题目别人已经做得很细了。所以赶快销尸灭迹
简单介绍一下别人怎么做。思路：至少会有两个居民点在所要圆的圆周上。对所有居民点（或是用convex hull算法过滤后的居民点）求最远点Voronoi图。所要圆的圆心必定位于该Voronoi图的顶点或边上。这样一来，整个问题就转化为对给定点集求Voronoi图。
具体程序也有现成的，这里推荐LEDA，它是用C++写成的STD库。感兴趣的可以看下面的程序举例。有觉得能做得比LEDA好的站出来
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/rat_circle.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>
using namespace leda;
int main()
{
list<rat_point> L;
random_points_in_square(10,50,L);
rat_circle C;
C=SMALLEST_ENCLOSING_CIRCLE(L);
window W;
W.init(-110,110,-110);
W.open(); W.display();
W.set_node_width(3);
W.set_line_width(2);
rat_point p;
forall(p,L) W.draw_filled_node(p.to_point());
W.draw_circle(C.to_circle(),red);
W.read_mouse();
W.screenshot("extremal_circle");
return 0;
}
想像一个三角形，如果我没理解错的话，你是以三边中的长边的中点作为圆心。对于钝角或直角三角形成立，对锐角三角形显然不成立。此时符合题意的点应当是外接圆的圆心。不在边上。
另外你的步骤一好像应该想寻找凸包，剔除内部点吧？如果是的话应该是正确的一步。显然有：
1.发射塔必然在凸包内
2.能覆盖凸包的顶点也必定能覆盖凸包内部的点
凸包有很多标准算法，可以自己搜索
本帖一共被 1 帖 引用 (帖内工具实现)
首先计算出包含所有点的一个convex hull，然后在这个convex hull上找出两个顶点，使得它们之间的距离最大。找到这两个顶点后，以这两点的中点为圆心，以顶点到中点点距离为半径，做圆。
这里面我说到了convex hull，应该是第一步。
那么对于只有三个点的简单情况，在锐角三角形的情况下，你所说的方法不对。
再找经过这四个偏散点最大的圆
还是要用凸包。在凸包上找出距离最远的两个点，然后求所有其它点到这两点的夹角，取夹角最小的那个点，和这两点做三角形。该三角形的“外心”（外接圆的圆心）就是你要的结果。
还是用一个三角形，如果是一个钝角三角形呢？那么外心在三角形外，简单画画就知道此时要找的点不是外心，而简单就是长边的中点。
综合一下应该是答案了吧：
1.找凸包
2.找最长连线的两点
3.凸包上其他点按与上述两点间的夹角排序
4.找到最小夹角（必然大于60，否则断言错误）
5.如果夹角小于90，取此三点外接圆圆心；否则取两点中点
有没有错误？
1.如果只有三个点呢？
2.即使有四个点，你拿北京，天津，石家庄和广州四个城市为例试试
看看是不是在对角线交点上。