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)

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)

*/

這樣也可以

        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

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)
*/