算法以覆盖点的最大数量与给定半径的一圈 [英] Algorithm to cover maximal number of points with one circle of given radius

问题描述

让我们想象一下，我们有它的一些点的飞机。 我们也有给定半径的圆。

Let's imagine we have a plane with some points on it. We also have a circle of given radius.

我需要一个算法来决定，它覆盖的点的最大可能数圈的这种地位。当然，也有很多这样的位置，所以算法应该返回他们中的一个。
precision并不重要，该算法可以做小的失误。

I need an algorithm that determines such position of the circle that it covers maximal possible number of points. Of course, there are many such positions, so the algorithm should return one of them.
Precision is not important and the algorithm may do small mistakes.

下面是一个例子图片：

Here is an example picture:

输入：
＆NBSP;＆NBSP; INTñ（N＆LT; = 50）＆ndash的;点的数目;
＆NBSP;＆NBSP; 浮法X [N] 和浮动Y [N] ＆ndash的;阵列点'X和Y坐标;
＆NBSP;＆NBSP; 浮动 - [R ＆ndash的;半径的圆的。

Input:
  int n (n<=50) – number of points;
  float x[n] and float y[n] – arrays with points' X and Y coordinates;
  float r – radius of the circle.

输出：
＆NBSP;＆NBSP; 浮法CX 和浮动CY ＆ndash的;协调圆的中心

Output:
  float cx and float cy – coordinates of the circle's center

闪电算法的速度，但应该不会太慢（因为我知道了一些缓慢的解决方案，这种情况下）。

Lightning speed of the algorithm is not required, but it shouldn't be too slow (because I know a few slow solutions for this situation).

C ++ code是preferred，但不是强制性的。

C++ code is preferred, but not obligatory.

推荐答案

编辑，以更好的措辞，如建议：

Edited to better wording, as suggested :

基本意见：

• 我假设半径是其中之一，因为它不会改变任何东西。
• 在给定的任意两点，有对他们撒谎存在最多两个单元的圈子。
• 给出解决办法圆你的问题，你可以将它，直到它包含两个点的集合，同时保持里面的设定点的相同。

的算法是，则：

• 对于每对点，如果它们的距离为＆lt; 2，计算两个单位圆C1和C2穿过它们。
• 计算您所设定的内部C1和C2的点数
• 取最大值。

这篇关于算法以覆盖点的最大数量与给定半径的一圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！