---
# System prepended metadata

title: 1610. Maximum Number of Visible Points
tags: [Leetcode, Hard, Math]

---

# 1610. Maximum Number of Visible Points
###### tags: `Leetcode` `Hard` `Math`
Link: https://leetcode.com/problems/maximum-number-of-visible-points/description/
## 思路
直觉上来讲 我们只需要找到所有点对于location的角度 排序 然后sliding window就能找到答案
但是会有如下几个问题:
1. 用```Math.atan2()```计算角度 return value的范围是```[-pi,pi]```
2. “首尾相接”。因为视野角度接近360度的目标点，与视野角度接近0度的目标点，其真实角度差范围并不大。那么我们如果寻找一个滑窗使得能够同时覆盖这两部分的点呢？处理的方法很常见，那就是将所有目标点的视野角度复制一遍、加上```2pi```、并拼接在```angles```数组后面。这样相当于```angles```数组里面有2n个目标点，视野范围是```[0,4pi]```。对于任何跨越过360角的滑窗，都可以覆盖到原先接近0度角的那些点。
3. 有一些point跟location重合 不论怎么转都可以覆盖到那些点
## Code
```java=
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int same = 0;
        double pi = 3.1415926;
        for(int i=0; i<points.size(); i++){
            List<Integer> point = points.get(i);
            if(point.get(0)==location.get(0) && point.get(1)==location.get(1)) same++;
            else{
                double alpha = Math.atan2(point.get(1)-location.get(1), point.get(0)-location.get(0));
                angles.add(alpha);
            }
        }
        Collections.sort(angles);
        int n = angles.size();
        for(int i=0; i<n; i++){
            angles.add(angles.get(i)+2*pi);
        }
        int ans = 0, j = 0;
        for(int i=0; i<2*n; i++){
            while(j<2*n && angles.get(j)-angles.get(i)<=angle*pi/180){
                j++;
            }
            ans = Math.max(ans, j-i);
        }
        return ans+same;
    }
}
```