现在二维坐标系里面有n个点,第i个点的坐标为(xi,yi)。
求在二维坐标系里面选择一个恰当的坐标作一个半径为r的圆，包含的点集的元素个数最多。

输入:
第一行输入两个数，第一个数是点个数n，第二个数是圆的半径r，两个输入之间用空格隔开。
然后接下来n行每行输入两个数，第一个数是第i个点的横坐标，第二个数是第i个点的纵坐标，两个输入之间用空格隔开。
输出:一行，该圆能够包含的点集的元素最大个数。

例子:
输入:
9 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
输出:
5

感觉这题思路应该是进行边界检测~想到思路的是求对每个点用动圆来边界检测其圆内包含点的个数。
但感觉把面量化成点来检验很有难度~现在我往如何才能把面量化为点来检验这个方面去想。
~感觉这题和平面几何有关系啊~不过还是对具体解法不清楚~具体怎么实现就说不出来了~这题感觉难度很大~现在我对解出这题的期望也不太高~不过还是可以尽量尝试一下吧~~~

如果选址在点上当然简单~但问题是选址不一定在题目给出的某个点上~圆心可以是二维空间的任意位置~这个才是棘手的地方。

想了很久想到了一种数学解法，对每个点进行分析，在选取点i上画一个半径为2r的圆，然后搜索其在2r里面的点。找到该点j再画一个半径为r的圆~这个圆会与以点i为圆心r为半径的圆有一个或者两个交点。按顺时针记录其中一个交点为记作+，另一个交点为-，遇到+就把max+1，遇到-就把max-1。然后统计该圆里面的max的最大值。

对所有点逐一比对~求这个max的最大值。

时间复杂度和点的稠密与否直接相关。

感觉为0(K*n^2)~~K为每个圆最多平均包含的点数~

[此贴子已经被作者于2017-4-22 04:51编辑过]

和二楼一并回复~这样大概看看不出什么问题~这个方法可以考虑验证一下~如果该方法成立则代码比我想到的那个更优更简了~~~~~

是的~算法复杂度和我想到的一样~感觉解法比我想到的要简单一些~这个代码虽然还没细测~但应该可以~

这是一个等边三角形~
难怪看了代码看了很久还是理解不了……感觉是方法问题~这题感觉没那么简单~~~~

顺便更新一下四楼的思路~

就是选一个定点，求该定点能被圆包含的点集的最大子集。该点在动圆上的圆心轨迹为半径r的圆i。以这个点作一个半径为2r的圆j，遍历该范围包含的点作一个圆k，k和i的轨迹有一个或者两个交点。选其cos值与垂直方向夹角小的画一个圆l，然后再遍历该圆l里面的点集。

就是求所有圆l里面点集的最大值。~这算法复杂度应该介于0(n^2/2)到0(n^3/2)之间(按逐个逐个点插入优化效率可以提高到原来的两倍)~圆越大算法复杂度越高~~

知道方法了折腾了半天竟然得出了如此简单有力的思维方法~~~~~~~~

已知圆的半径和两个定点能确定一个或者两个定圆，这个圆也有可能不存在的~~然后找到该圆心遍历点集是否在圆内~就是进行边界检测~
经过优化选方程的两个解其中之一算法复杂度也是在0(n^2/2)到0(n^3/2)之间~其实实质就是11楼的另一种说法~~

[此贴子已经被作者于2017-4-22 06:14编辑过]

对哦~有道理~想到了~一个点表示一个圆~两个点表示两个圆~两个圆的交集区域就是表示能包含两个点的区域~其实就是求重合区域的最大重合次数~两个圆的的弦必然在这个交集里面~新增一个(点)圆~就会有三条公共弦~就是求这些公共弦的交点有包含了多少个点~这个逻辑上是行得通的~

说个题外话~神奇的是三条公共弦实际如果有交点实际上只有一个交点~这个交点似乎是三个圆的六个交点外三个交点组成的和里面三个组成的三角形的什么心~~以前想利用平面几何证明~无奈变量太多做不了(后来看到网上有高手能用简洁的数学语言证明出来就笑哭了)~~

[此贴子已经被作者于2017-4-24 06:04编辑过]

100分全送你了~~~~~~~现在还有别的任务----无论是编程任务还是学习任务~~~代码找到时间再慢慢细测~~~~

感觉原理上没有错~不过我看了13楼的代码还是有一个疑问~公共弦应该是一条线段而不是一条直线~所以13楼代码说是求两条直线的交点到到两个端点的任意一个距离是否大于该线段长度这个条件判断？~我没有细看代码~如果代码有考虑此情况就原谅我多问了~~


PS:这条题方法还可以再改进一下~可以不用求直线表达式~就是求两个圆的交点能被多少个圆包含~这样理解就变得非常简单了~~~~~~~~~

[此贴子已经被作者于2017-4-24 06:45编辑过]