//昨天的每日一题,昨天顾着玩忘了今天补上
给你一个点数组 points 和一个表示角度的整数 angle ,你的位置是 location ,其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始,你面向东方进行观测。你 不能 进行移动改变位置,但可以通过 自转 调整观测角度。换句话说,posx 和 posy 不能改变。你的视野范围的角度用 angle 表示, 这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数,那么你的视野就是角度范围 [d – angle/2, d + angle/2] 所指示的那片区域
对于每个点,如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 ,那么你就可以看到它。
同一个坐标上可以有多个点。你所在的位置也可能存在一些点,但不管你的怎么旋转,总是可以看到这些点。同时,点不会阻碍你看到其他点。
返回你能看到的点的最大数目。
对我来说又是一道CV题
也是我刷题生涯里第一次遇到几何题
虽然我很快的想到了要用极坐标来算
但是具体操作起来就萎了
问题一:题目中极坐标相对的不再是(0,0)而是location
因为正常思路我们肯定要想到用反三角函数来求出对应的极角
但是都是相对于原点来说的
而且范围基本是在0~PI
所以这里需要注意
问题二:计算完极角后需要排序然后二分查找
这里要小心坐标翻转的情况
public class Solution { public int VisiblePoints(IList<IList<int>> points, int angle, IList<int> location) { int sameCnt = 0; List<double> polarDegrees = new List<double>(); int locationX = location[0]; int locationY = location[1]; for (int i = 0; i < points.Count; ++i) { int x = points[i][0]; int y = points[i][1]; if (x == locationX && y == locationY) { sameCnt++; continue; } double degree = Math.Atan2(y - locationY, x - locationX); polarDegrees.Add(degree); } polarDegrees.Sort(); int m = polarDegrees.Count; for (int i = 0; i < m; ++i) { polarDegrees.Add(polarDegrees[i] + 2 * Math.PI); } int maxCnt = 0; double toDegree = angle * Math.PI / 180.0; for (int i = 0; i < m; ++i) { int iteration = BinarySearch(polarDegrees, polarDegrees[i] + toDegree, false); maxCnt = Math.Max(maxCnt, iteration - i); } return maxCnt + sameCnt; } public int BinarySearch(List<double> nums, double target, bool lower) { int left = 0, right = nums.Count - 1; int ans = nums.Count; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/maximum-number-of-visible-points/solution/you-xiao-ke-jian-dian-de-zui-da-shu-mu-b-r1qz/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。