1610-可见点的最大数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。

最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，posx 和 posy
不能改变。你的视野范围的角度用 angle 表示， 这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数，那么你的视野就是角度范围
[d - angle/2, d + angle/2] 所指示的那片区域。

Your browser does not support the video tag or this video format.

对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 ，那么你就可以看到它。

同一个坐标上可以有多个点。你所在的位置也可能存在一些点，但不管你的怎么旋转，总是可以看到这些点。同时，点不会阻碍你看到其他点。

返回你能看到的点的最大数目。

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/10/04/89a07e9b-00ab-4967-976a-c723b2aa8656.png)

**输入：** points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
**输出：** 3
**解释：** 阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。

示例 2：

**输入：** points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
**输出：** 4
**解释：** 在你的视野中，所有的点都清晰可见，包括你所在位置的那个点。

示例 3：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/10/04/5010bfd3-86e6-465f-ac64-e9df941d2e49.png)

**输入：** points = [[1,0],[2,1]], angle = 13, location = [1,1]
**输出：** 1
**解释：** 如图所示，你只能看到两点之一。

提示：

  • 1 <= points.length <= 105
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi <= 100

方法一：二分查找

思路

题目本身为几何问题，需要求出在视角范围内 [d - \textit{angle} / 2, d + \textit{angle} / 2] 内最多的点的覆盖数。在本题中视角可转换为相对于 location 的「极角 」。首先将所有点 p 的坐标转化为相对于 location 的极角，设点 p 相对于 location 的极角为 d_{p，找到坐标的极角处于区间 [d_{p},d_{p} + \textit{angle}] 的最大数量即可。

  • 极角转换时，已知两点的坐标可以通过反三角函数来进行转换，一般可以通过反余弦 acos，反正弦 asin，反正切 atan 等函数来确定，但以上函数的返回值范围最多只能覆盖 \pi，可以利用函数 atan2，不同的语言实现可以参考不同语言的标准库函数。以 C++ 为例，「atan2 」的返回值范围为 [-\pi,\pi]，它的覆盖范围为 2\pi。

  • 我们将所有坐标的相对于 location 极角全部求出，并按照极角的大小进行排序，我们遍历每个坐标 p_i = (x_i,y_i)，我们设 p_i 的相对于 location 的极角为 d_{p_i，此时需要求出所有满足坐标的极角大小处在 [d_{p_i},d_{p_i} + \textit{angle}] 范围内的最大数目，可以利用二分查找快速的统计出处在 [d_{p_i},d_{p_i} + \textit{angle}] 的元素数目。特别注意的是，由于存在 d_{p_i} + \textit{angle} > 180\degree 的情况，可以在原数组中将每个元素 d_{p_i} + 360\degree 添加到原数组的后面，这样即可防止反转的问题。

  • 在求极角时，对于坐标刚好处于 location 的元素需要单独进行统计，因为当 atan2 的两个参数都为 0 时，atan2 的返回值可能是未定义的，因此我们要尽量避免这种情况发生，所以需要将位于 location 的坐标进行单独统计。

代码

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int sameCnt = 0;
        List<Double> polarDegrees = new ArrayList<>();
        int locationX = location.get(0);
        int locationY = location.get(1);
        for (int i = 0; i < points.size(); ++i) {
            int x = points.get(i).get(0);
            int y = points.get(i).get(1);
            if (x == locationX && y == locationY) {
                sameCnt++;
                continue;
            }
            Double degree = Math.atan2(y - locationY, x - locationX);
            polarDegrees.add(degree);
        }
        Collections.sort(polarDegrees);

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.add(polarDegrees.get(i) + 2 * Math.PI);
        }

        int maxCnt = 0;
        Double toDegree = angle * Math.PI / 180;
        for (int i = 0; i < m; ++i) {
            int iteration = binarySearch(polarDegrees, polarDegrees.get(i) + toDegree, false);
            maxCnt = Math.max(maxCnt, iteration - i);
        }
        return maxCnt + sameCnt;
    }

    public int binarySearch(List<Double> nums, Double target, boolean lower) {
        int left = 0, right = nums.size() - 1;
        int ans = nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums.get(mid) > target || (lower && nums.get(mid) >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        int sameCnt = 0;
        vector<double> polarDegrees;
        for (auto & point : points) {
            if (point[0] == location[0] && point[1] == location[1]) {
                sameCnt++;
                continue;
            }
            double degree = atan2(point[1] - location[1], point[0] - location[0]);
            polarDegrees.emplace_back(degree);
        }
        sort(polarDegrees.begin(), polarDegrees.end());

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.emplace_back(polarDegrees[i] + 2 * M_PI);
        }

        int maxCnt = 0; 
        double degree = angle * M_PI / 180;
        for (int i = 0; i < m; ++i) {
            auto it = upper_bound(polarDegrees.begin() + i, polarDegrees.end(), polarDegrees[i] + degree);
            int curr = it - polarDegrees.begin() - i;
            maxCnt = max(maxCnt, curr);
        }
        return maxCnt + sameCnt;
    }
};
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define PI 3.1415926
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int cmp(const void* a, const void* b) {
    double* pa = (double*)a;
    double* pb = (double*)b;
    return *pa > *pb ? 1 : -1;
}

int binarySearch(double* nums, int numsSize, double target, bool lower) {
    int left = 0, right = numsSize - 1;
    int ans = 0;
    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;
}

int visiblePoints(int** points, int pointsSize, int* pointsColSize, int angle, int* location, int locationSize){
    int sameCnt = 0;
    int polarSize = 0;
    double* polarDegrees = (double*)malloc(sizeof(double) * pointsSize * 2);
    for (int i = 0; i < pointsSize; ++i) {
        if (points[i][0] == location[0] && points[i][1] == location[1]) {
            sameCnt++;
            continue;
        }
        double degree = atan2(points[i][1] - location[1], points[i][0] - location[0]);
        polarDegrees[polarSize] = degree;
        polarSize++;
    }
    qsort(polarDegrees, polarSize, sizeof(double), cmp);

    int m = polarSize;
    for (int i = 0; i < m; ++i) {
        polarDegrees[polarSize] = polarDegrees[i] + 2 * PI;
        polarSize++;
    }

    int maxCnt = 0; 
    double degree = angle * PI / 180.0;
    for (int i = 0; i < m; ++i) {
        int iteration = binarySearch(polarDegrees, polarSize, polarDegrees[i] + degree, false);
        maxCnt = MAX(maxCnt, iteration - i);
    }
    return maxCnt + sameCnt;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var visiblePoints = function(points, angle, location) {
    let sameCnt = 0;
    const polarDegrees = [];
    let locationX = location[0];
    let locationY = location[1];
    for (let i = 0; i < points.length; ++i) {
        const x = points[i][0];
        const y = points[i][1];
        if (x === locationX && y === locationY) {
            sameCnt++;
            continue;
        }
        const degree = Math.atan2(y - locationY, x - locationX);
        polarDegrees.push(degree);
    }
    polarDegrees.sort((a, b) => a - b);

    const m = polarDegrees.length;
    for (let i = 0; i < m; ++i) {
        polarDegrees.push(polarDegrees[i] + Math.PI * 2);
    }

    let maxCnt = 0;
    const toDegree = angle * Math.PI / 180; 
    for (let i = 0; i < m; ++i) {
        const iteration = binarySearch(polarDegrees, polarDegrees[i] + toDegree, false);
        maxCnt = Math.max(maxCnt, iteration - i);
    }
    return maxCnt + sameCnt;
};

const binarySearch = (nums, target, lower) => {
    let left = 0, right = nums.length - 1;
    let ans = nums.length;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func visiblePoints(points [][]int, angle int, location []int) int {
    sameCnt := 0
    polarDegrees := []float64{}
    for _, p := range points {
        if p[0] == location[0] && p[1] == location[1] {
            sameCnt++
        } else {
            polarDegrees = append(polarDegrees, math.Atan2(float64(p[1]-location[1]), float64(p[0]-location[0])))
        }
    }
    sort.Float64s(polarDegrees)

    n := len(polarDegrees)
    for _, deg := range polarDegrees {
        polarDegrees = append(polarDegrees, deg+2*math.Pi)
    }

    maxCnt := 0
    degree := float64(angle) * math.Pi / 180
    for i, deg := range polarDegrees[:n] {
        j := sort.Search(n*2, func(j int) bool { return polarDegrees[j] > deg+degree })
        if j-i > maxCnt {
            maxCnt = j - i
        }
    }
    return sameCnt + maxCnt
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        sameCnt = 0
        polarDegrees = []
        for p in points:
            if p == location:
                sameCnt += 1
            else:
                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))
        polarDegrees.sort()

        n = len(polarDegrees)
        polarDegrees += [deg + 2 * pi for deg in polarDegrees]

        degree = angle * pi / 180
        maxCnt = max((bisect_right(polarDegrees, polarDegrees[i] + degree) - i for i in range(n)), default=0)
        return maxCnt + sameCnt

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为坐标的个数，由于需要对所有的极角进行排序，再对每一个坐标的区间进行二分查找，因此总的时间复杂度应该为 O(n \log n + 2n \log (2n)) = O(n \log n)。

  • 空间复杂度：O(n)，其中n 为坐标的个数，我们总共最多需要两倍坐标个数的空间来存储坐标的极角。

方法二：滑动窗口

思路

整体解题思路跟方法一类似，在进行区间查找时，可以利用滑动窗口对每个坐标的极角区间 [d_{p_i},d_{p_i} + \textit{angle}] 查找的时间复杂度由 O(2n \log 2n) 优化为 O(2n + 2n)。

代码

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int sameCnt = 0;
        List<Double> polarDegrees = new ArrayList<>();
        int locationX = location.get(0);
        int locationY = location.get(1);
        for (int i = 0; i < points.size(); ++i) {
            int x = points.get(i).get(0);
            int y = points.get(i).get(1);
            if (x == locationX && y == locationY) {
                sameCnt++;
                continue;
            }
            Double degree = Math.atan2(y - locationY, x - locationX);
            polarDegrees.add(degree);
        }
        Collections.sort(polarDegrees);

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.add(polarDegrees.get(i) + 2 * Math.PI);
        }

        int maxCnt = 0;
        int right = 0;
        double toDegree = angle * Math.PI / 180; 
        for (int i = 0; i < m; ++i) {
            Double curr = polarDegrees.get(i) + toDegree;
            while (right < polarDegrees.size() && polarDegrees.get(right) <= curr) {
                right++;
            }
            maxCnt = Math.max(maxCnt, right - i);
        }
        return maxCnt + sameCnt;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        int sameCnt = 0;
        vector<double> polarDegrees;
        for (auto & point : points) {
            if (point[0] == location[0] && point[1] == location[1]) {
                sameCnt++;
                continue;
            }
            double degree = atan2(point[1] - location[1], point[0] - location[0]);
            polarDegrees.emplace_back(degree);
        }
        sort(polarDegrees.begin(), polarDegrees.end());

        int m = polarDegrees.size();
        for (int i = 0; i < m; ++i) {
            polarDegrees.emplace_back(polarDegrees[i] + 2 * M_PI);
        }

        int maxCnt = 0;
        int right = 0;
        double degree = angle * M_PI / 180;
        for (int i = 0; i < m; ++i) {
            while (right < polarDegrees.size() && polarDegrees[right] <= polarDegrees[i] + degree) {
                right++;
            }
            maxCnt = max(maxCnt, right - i);
        }
        return maxCnt + sameCnt;
    }
};
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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;
        int right = 0;
        double toDegree = angle * Math.PI / 180;
        for (int i = 0; i < m; ++i) {
            double curr = polarDegrees[i] + toDegree;
            while (right < polarDegrees.Count && polarDegrees[right] <= curr) {
                right++;
            }
            maxCnt = Math.Max(maxCnt, right - i);
        }
        return maxCnt + sameCnt;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define PI 3.1415926
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int cmp(const void* a, const void* b) {
    double* pa = (double*)a;
    double* pb = (double*)b;
    return *pa > *pb ? 1 : -1;
}

int visiblePoints(int** points, int pointsSize, int* pointsColSize, int angle, int* location, int locationSize){
    int sameCnt = 0;
    int polarSize = 0;
    double* polarDegrees = (double*)malloc(sizeof(double) * pointsSize * 2);
    for (int i = 0; i < pointsSize; ++i) {
        if (points[i][0] == location[0] && points[i][1] == location[1]) {
            sameCnt++;
            continue;
        }
        double degree = atan2(points[i][1] - location[1], points[i][0] - location[0]);
        polarDegrees[polarSize] = degree;
        polarSize++;
    }
    qsort(polarDegrees, polarSize, sizeof(double), cmp);

    int m = polarSize;
    for (int i = 0; i < m; ++i) {
        polarDegrees[polarSize] = polarDegrees[i] + 2 * PI;
        polarSize++;
    }

    int maxCnt = 0; 
    int right = 0;
    double toDegree = angle * PI / 180;
    for (int i = 0; i < m; ++i) {
        while (right < polarSize && polarDegrees[right] <= polarDegrees[i] + toDegree) {
            right++;
        }
        maxCnt = MAX(maxCnt, right - i);
    }
    return maxCnt + sameCnt;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var visiblePoints = function(points, angle, location) {
    let sameCnt = 0;
    const polarDegrees = [];
    let locationX = location[0];
    let locationY = location[1];
    for (let i = 0; i < points.length; ++i) {
        const x = points[i][0];
        const y = points[i][1];
        if (x === locationX && y === locationY) {
            sameCnt++;
            continue;
        }
        const degree = Math.atan2(y - locationY, x - locationX);
        polarDegrees.push(degree);
    }
    polarDegrees.sort((a, b) => a - b);

    const m = polarDegrees.length;
    for (let i = 0; i < m; ++i) {
        polarDegrees.push(polarDegrees[i] + 2 * Math.PI);
    }

    let maxCnt = 0;
    let right = 0;
    const toDegree = angle * Math.PI / 180;
    for (let i = 0; i < m; ++i) {
        const curr = polarDegrees[i] + toDegree;
        while (right < polarDegrees.length && polarDegrees[right] <= curr) {
            right++;
        }
        maxCnt = Math.max(maxCnt, right - i);
    }
    return maxCnt + sameCnt;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func visiblePoints(points [][]int, angle int, location []int) int {
    sameCnt := 0
    polarDegrees := []float64{}
    for _, p := range points {
        if p[0] == location[0] && p[1] == location[1] {
            sameCnt++
        } else {
            polarDegrees = append(polarDegrees, math.Atan2(float64(p[1]-location[1]), float64(p[0]-location[0])))
        }
    }
    sort.Float64s(polarDegrees)

    n := len(polarDegrees)
    for _, deg := range polarDegrees {
        polarDegrees = append(polarDegrees, deg+2*math.Pi)
    }

    maxCnt := 0
    right := 0
    degree := float64(angle) * math.Pi / 180
    for i, deg := range polarDegrees[:n] {
        for right < n*2 && polarDegrees[right] <= deg+degree {
            right++
        }
        if right-i > maxCnt {
            maxCnt = right - i
        }
    }
    return sameCnt + maxCnt
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        sameCnt = 0
        polarDegrees = []
        for p in points:
            if p == location:
                sameCnt += 1
            else:
                polarDegrees.append(atan2(p[1] - location[1], p[0] - location[0]))
        polarDegrees.sort()

        n = len(polarDegrees)
        polarDegrees += [deg + 2 * pi for deg in polarDegrees]

        maxCnt = 0
        right = 0
        degree = angle * pi / 180
        for i in range(n):
            while right < n * 2 and polarDegrees[right] <= polarDegrees[i] + degree:
                right += 1
            maxCnt = max(maxCnt, right - i)
        return sameCnt + maxCnt

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为坐标的个数，由于需要对所有的极角进行排序，利用移动指针区间查找的时间复杂度为 O(2n + 2n)，因此总的时间复杂度应该为 O(n \log n + 2n + 2n) = O(n \log n)。

  • 空间复杂度：O(n)，其中 n 为坐标的个数，我们总共最多需要两倍坐标个数的空间来存储坐标的极角。

 Comments
On this page
1610-可见点的最大数目