力扣每日一题2021-12-16困难题：可见点的最大数目

力扣每日一题2021-12-16困难题：可见点的最大数目

可见点的最大数目

• 1610.可见点的最大数目
• • 题目描述
  • 思路
  • • 双指针
    • • Java实现
      • Python实现

---

1610.可见点的最大数目 题目描述

可见点的最大数目

---

思路 双指针

根据题意，需要求出在施教范围内最多的点的覆盖数。以location为原点，根据点之间的横坐标差和纵坐标差，计算弧度，再把弧度换算成角度。
将得到的点排序，双指针进行滑动窗口，滑窗的限制是最大角减最小角不得大于固定的angle角度。

Java实现

class Solution {
    private int base;
    private int x, y;
    public int visiblePoints(List> points, int angle, List location) {
        base = 0; 
        x = location.get(0); 
        y = location.get(1);
        List angles = new ArrayList<>();
        for(List point: points){
            double degree = helper(point);
            if(degree >= 0)
                angles.add(degree);
        }
        Collections.sort(angles);
        int s = angles.size();
        for(int i=0;i 0 ? 90.0 : 270.0;
        if(dy == 0)
            return dx > 0 ? 0.0 : 180.0;
        if(dx * dy > 0)
            return Math.toDegrees(Math.atan((double)dy/dx))+(dx > 0 ? 0.0 : 180.0);
        return Math.toDegrees(Math.atan(-(double)dx/dy)) + (dy > 0 ? 90.0 : 270.0);
    }
}

Python实现

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        self.base = 0
        def helper(point):
            dx, dy = point[0] - location[0], point[1] - location[1]
            if not dx and not dy:
                self.base += 1
                return None
            if not dx:
                return 90 if dy > 0 else 270
            if not dy:
                return 0 if dx > 0 else 180
            if dx * dy > 0:
                return math.degrees(math.atan(dy/dx)) + (0 if dx > 0 else 180)
            return math.degrees(math.atan(-dx/dy)) + (90 if dx < 0 else 270)
        
        angles = []
        for p in points:
            degree = helper(p)
            if degree is not None:
                angles.append(degree)
        angles.sort()
        angles = angles + [360 + a for a in angles]
        l = r = ans = 0
        while l < len(angles):
            while r < len(angles) and angles[r] - angles[l] <= angle:
                r += 1
            ans = max(ans, r - l)
            l += 1
        return ans + self.base