每日一题——1610. 可见点的最大数目

1610. 可见点的最大数目

//昨天的每日一题，昨天顾着玩忘了今天补上

给你一个点数组 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。