落在圆型区域内的最大数量 算法实现

landsat99

条件描述：
一名射击运动员向一面墙射击。给出一个数组darts ，其中darts = [xi, yi] 表示此运动员的第 i 次射击弹孔的位置。
裁判知道墙面上所有 n 次弹孔的位置。他想要往墙面上放置一个半径为 r 的圆型靶标，使运动员的弹孔尽可能多地落在圆型靶标上。

问题：
给定整数 r ，请找出能够落在半径为r的圆型靶标上的最大弹孔数。


示例 1 ：

输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的弹孔都落在靶上，此时落在靶上的弹孔数最大，值为 4 。



示例 2 ：


输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的弹孔都落在靶上，此时落在靶上的弹孔数最大，值为 5 。

mahuan1279

有点儿像最小外接圆，又有些像聚类。用随机算法可以快速得到近优解，但不能保证就是最优解。

mahuan1279

显然肯定有2个点在覆盖圆的边界上。可以枚举任意2个点，求出以该两点连线为弦、半径为r的圆，再枚举每个点是否在圆内。复杂度O(N^3）。
还有另一算法：
对每个点以R为半径画圆，对N个圆两两求交。这一步O(N^2)。问题转化为求被覆盖次数最多的弧。
因为如果最优圆覆盖A点那么最优圆一定在以A点为圆心的圆弧上。那么圆弧倍覆盖多少次也就意味着
以这条圆弧为上任意一点为圆心花园能覆盖多少点。
对每一个圆，求其上的每段弧重叠次数。假如A圆与B圆相交。A上[PI/3, PI/2]的区间被B覆盖(PI为圆周率)。
那么对于A圆，我们在PI/3处做一个+1标记，在PI/2处做一个-1标记。
对于[PI*5/3, PI*7/3]这样横跨0点的区间只要在0点处拆成两段即可。
将一个圆上的所有标记排序，从头开始扫描。初始total=0，碰到+1标记给total++，碰到-1标记total–。
扫描过程中total的最大值就是圆上被覆盖最多的弧。求所有圆的total的最大值就是答案。
极角排序需要2*n*logn，总复杂度O(N^2 * logN)
————————————————
版权声明：本文为CSDN博主「ramay7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Ramay7/article/details/51147778

landsat99

mahuan1279 发表于 2023-2-27 09:30
显然肯定有2个点在覆盖圆的边界上。可以枚举任意2个点，求出以该两点连线为弦、半径为r的圆，再枚举每个点 ...

赞一个

1. 定半径的相交弧角分析，思路相当巧，时间复杂度也优异。好算法。
2.  定半径 两点定圆，算法直观。另外此方案有扩展性优势，非圆的多边形也基本适用。

mahuan1279

landsat99 发表于 2023-2-28 09:03
赞一个

1. 定半径的相交弧角分析，思路相当巧，时间复杂度也优异。好算法。

你最近是在研究算法问题吗？还是在刷算法题？

landsat99

非IT方向。基础几何算法的工程力学应用  作为图形处理核心之一，往往是思路各异，各有千秋。某些有代表性的问题能和大家一起讨论，收益匪浅

mahuan1279

landsat99 发表于 2023-2-28 10:33
非IT方向。基础几何算法的工程力学应用  作为图形处理核心之一，往往是思路各异，各有千秋。某些有代表性的 ...

刷刷力扣题很有好处。

landsat99

mahuan1279 发表于 2023-2-28 12:33
刷刷力扣题很有好处。

和各位大咖们一起学习讨论

mahuan1279

landsat99 发表于 2023-2-28 18:28
和各位大咖们一起学习讨论

共同学习，锻炼思维。