# 1610. Maximum Number of Visible Points

can refer this:

<https://leetcode.com/problems/maximum-number-of-visible-points/discuss/1595464/Java-oror-Sliding-Window-oror-Change-to-Degree-oror-Explained-Thoroughly>

```
T: O(nlogn), n is length of points
S: O(n)
```

```java
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int same = 0;
        for (List<Integer> point : points) {
            // 被觀察的點 x, y - 看的地方的座標
            int dx = point.get(0) - location.get(0);
            int dy = point.get(1) - location.get(1);
            
            // 有些點可能是重合的, 代表 不管什麼角度 都看得到這些點
            // 所以單獨計算, 最後加到結果
            if (dx == 0 && dy == 0) {
                same++;
            } else {
                // 得到各點, 各距離的角度
                double degree = Math.atan2(dy, dx)*(180/Math.PI);
                angles.add(degree);
            }
        }
        // 排序一下
        Collections.sort(angles);
        
        // for circular 處理, 因為在尾端 sliding window 可能處理不到, 所以需要
        // n 記得要提出來, 不然會跟著變大...因為再加資料
        int n = angles.size();
        for (int i = 0; i < n; i++) { 
            angles.add(angles.get(i)+360); // append 一樣的 degree 但都多家 360
        }
        
        // sliding window
        int res = 0;
        int right = 0;
        for (int left = 0; left < angles.size(); left++) {
            while (right < angles.size() && angles.get(right) - angles.get(left) <= angle) {
                right++;
            }
            res = Math.max(res, right - left);
        }
        return res + same;
    }
}

/*
ex:
left
           right
[10,20, 29]
angle = 30

cal each point dx. dy (points to location's dist)

use dx. dy get angles list (degree = Math.atan2(dy, dx)*(180/Math.PI))

sort angles list 

handle circular issue: for i = 0~n, append each angles with +360 degree

then do the sliding window, window size = angle

T: O(nlogn), n is length of points
S: O(n)

*/
```

這樣也可以

```java
        int res = 0;
        int left = 0;
        for (int right = 0; right < angles.size(); right++) {
            if (left < angles.size() && angles.get(right) - angles.get(left) > angle) {
                left++;
            }
            // 因為求最大, 所以不用特別限制
            res = Math.max(res, right - left + 1);
        }
```

#### more explain

```java
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int sameCount = 0;
        for (List<Integer> point : points) {
            int dx = point.get(0) - location.get(0);
            int dy = point.get(1) - location.get(1);
            if (dx == 0 && dy == 0) {
                sameCount++;
            } else {
                double degree = Math.atan2(dy, dx)*(180/Math.PI);
                angles.add(degree);
            }
        }
        Collections.sort(angles);
        int n = angles.size();
        for (int i = 0 ; i < n; i++) {
            angles.add(angles.get(i)+360);
        }
        
        n = angles.size();
        int left = 0;
        int max = 0;
        for (int right = 0; right < n; right++) {
            if (left < n && angles.get(right) - angles.get(left) > angle) {
                left++;
            }
            max = Math.max(max, right - left + 1);
        }
        return max + sameCount;
    }
}

/*
question:
fix position (location)

Your field of view in degrees : rotate by angle

There can be multiple points at one coordinate.

count same:
There may be points at your location, and you can always see these points regardless of your rotation

Return the maximum number of points you can see.


idea: 

1.
base on the east 
cal the point's degree from east

for example 0,1 => 90 degree, 
how to cal degree? use Math.atan2(dy, dx)*(180/Math.PI)

dy, dx is the dist: dx: pointsX - locationX, dy: pointsY - locationY

so we'll have a list of degree, [359, 20, 100, 40]

2.
we can sort it, then do the sliding window(assume is angle = 30)

sort: [20, 40, 100, 359], T: O(nlogn)

but like [20, 359], it's really closed, if sliding window is 30, we can't cover [20, 359] this circular part

so handle the circular issue, append the same data with more 360 degree

[20, 40, 100, 359] + [20+360, 40+360, 100+360, 359+360]

=> [20, 40, 100, 359, 380, 400, 460, 719], angle = 30

3.
do sliding window, count "the max number"

4.
but there is one more edge case:
There may be points at your location, and you can always see these points regardless of your rotation

so if dist: dx == 0, dy == 0 , means what ever you rotate, always can see these points
=> count same number

in conclusion: 

ans: "the max number" + "same number"
              3
 0    1  2   right
[10, 15, 20, 30]
 [  20    ]
 
 3. 1. = 2 so need add 1
 
 T: O(nlogn)
 S: O(n)
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/two-pointer/sliding-window/1610.-maximum-number-of-visible-points.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.