本题的意思是说,以一个观测点为中心,视野可以360度旋转。你现在允许挑选一个视野范围angle,问最多能看到多少目标。
此题的入手比较容易,就是把所有目标点相对于观测点的角度都计算出来,排序后组成一个数组。然后找一段最长的滑窗(指的是包含的元素数目最多),使得滑窗范围内目标点的角度范围之差不超过angle。
本题的第一个考点是如何计算“目标点相对于观测点的角度”。我们希望这个相对于x正轴的角度分布是在[0,2*pi]上连续的。如果我们选择用atan(dy/dx)计算,得到的值域其实是[-pi/2,pi/2],我们要根据(x,y)的具体的象限位置再做调整。具体的是:
第一象限:atan(dy/dx)得到的是正数,所以 alpha = atan(dy/dx)
第二象限:atan(dy/dx)得到的是负数,所以 alpha = atan(dy/dx)+pi
第三象限:atan(dy/dx)得到的是正数,所以 alpha = atan(dy/dx)+pi
第三象限:atan(dy/dx)得到的是负数,所以 alpha = atan(dy/dx)+2*pi
这样四个象限的目标点的视野角度相对于x正轴而言的分布就是在[0,2*pi]上连续的。
另外一种方法是利用函数atan2(dy,dx),得到是(x,y)这个点相对于x正轴的“辐角主值”,值域范围是[-pi,pi]. 因为圆周对称,我们可以将这个“视野角度”整体加上pi转换成[0,2*pi],并不影响结果。
本题的第二个考点是“首尾相接”。因为视野角度接近360度的目标点,与视野角度接近0度的目标点,其真实角度差范围并不大。那么我们如果寻找一个滑窗使得能够同时覆盖这两部分的点呢?处理的方法很常见,那就是将所有目标点的视野角度复制一遍、加上2pi、并拼接在angles数组后面。这样相当于angles数组里面有2n个目标点,视野范围是[0,4pi]。对于任何跨越过360角的滑窗,都可以覆盖到原先接近0度角的那些点。
此题的第三个考点是:如果目标点与观测点完全重合,它可以算作任意的视野范围,所以我们需要把它们单独处理,不能放入angles数组内。我们要把这些点另外计入angles的最大滑窗里。