小编Jos*_*rke的帖子

我想知道一个返回true或false的算法,告诉我是否可以围绕一组点A绘制一个圆,这样点B组中的任何点都不在其中,或者反过来(可能)围绕一组点B绘制圆圈,使得来自点集A的任何点不在其内部).

基本上,你有两组点作为输入,你需要确定是否可以围绕任何一个绘制一个圆,这样另一个点的任何一个点都不在其中.

我已经看过Megiddo的线性时间算法来解决最小的圆周问题,但问题是它只绘制了最小的圆,这意味着它在你需要一个大圆的情况下不起作用.

这是我的意思的图片:

在这张图片中,可以围绕红点集绘制一个非常大的圆圈,这样任何一个绿点都不在其中,因此Megiddo的算法将无法工作.