UC知道这个算法如何设计？
来源：百度知道 编辑：UC知道 时间：2024/05/15 16:01:44
讲一下思路就行，尽量避免穷举法
To Chinaidea:这样不行，举个特例：有一圈点绕着原点，半径是10，那么重心就是原点了。但是如果给定矩形是1*2，放在原点无论怎样旋转都没用啊
To hzjsmart：很感谢你的热心回答，我刚才其实也是按这个方法作的，咱们不谋而合啊。不过我想看看有什么更好的方法，大家一起交流一下。
To k4me:矩形边上的点也算，等量情况随便给出一种解法就行，至于角度……同学你是数学系的吗？
To kusky:你的假设好像不成立。比如有三个点，而矩形包含其中两个，这样交点为1的边有两条，但是外面的点只有一个。
To zaijian2009,gunfdiy:穷举效率太低了，这是一道考题，肯定不能让你穷举的。
我的大概思路这样：
平面上有N个点。
根据假设“最优矩形包含第i个点”，可以把总问题分解为N个小问题。
在第i个小问题中，矩形必然包含第i个点。
为何称之为“小”问题呢。因为“距离大于矩形对角线长度的点不可能在同一矩形内”，所以每个“小”问题都不需要考虑全部N点，只需要考虑第i点为圆心，对角线长为半径内的若干个点，设K个点。，不同的小问题，K值一般是不同的。。
对于每个小问题，可以用穷举法，不断测试K个点中的某几个能否被矩形包容。
然后每个小问题找出一个能包含最多点的矩形，，最后在所有小问题中，选出包点最多的一个矩形，就可以了。
小问题由于包含的点少，所以求解应该相对快。具体解法有待进一步研究。
附带提出两个问题
A.界定.矩形线上的算在内还是在外.比如正方形四个角四个点,同尺寸的正方形来"圈",算4个点还是0个点.
B.等量.矩形在某处与另一处获得同样多的点.
C.解决问题中的角度问题,和穷举有关.角度可无限细分.夸张些假设,以10亿光年的矩形斜对角为半径来搜索平面中的星球数.角度差之毫厘,星球失之NNN.这不算什么极限问题,即使只有3个点也有可能产生严重冲突,恰巧某三点处于不断细分的角度左右振荡之间并且是无限小数...(多点的时候,冲突就更直接影响到真实数量)貌似不可解决:P
如果要在程序中实现，不知道函数PtInRect是否会有帮助。
如果是讨论算法的问题。我有以下思路。
n个点连成的n(n-1)/2条线段中，只与矩形有一个交点的线的数量等于矩形外部的点的数量。这样，与矩形只有一个交点的边的数量最少即为所求。
一个给定大小的矩形的四条边可表示为斜率k和一未知量b的方程。平面内各点坐标已知。二元方程求最优，似乎可解。
没有实践，不知是否可行。
看到了,进来看看.
好的办法我是没有,笨办法不知道能不能用..
随便那一个点A(x,y)
固定在矩形的顶点.然后旋转360度.
这么做可以覆盖点一周的以长方形斜边为半径的圆
也是它包含点A后,能覆盖最大的面积.
通过旋转360度来找出包含点数最多的