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

共:💬55 🌺26

放弃，彻底投降

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

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

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

#include <LEDA/core/list.h>

#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;

}

有趣有益，互惠互利；开阔视野，博采众长。
虚拟的网络，真实的人。天南地北客，相逢皆朋友