cpp 解法, 执行用时: 560 ms, 内存消耗: 160.3 MB, 提交时间: 2023-09-24 23:05:56

class Solution {
public:
    // 二分查找
    int visiblePoints2(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;
    }

    // 滑动窗口
    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;
    }
};

java 解法, 执行用时: 133 ms, 内存消耗: 95.1 MB, 提交时间: 2023-09-24 23:05:14

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;
    }

    // 二分查找
    public int visiblePoints2(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;
    }
}

javascript 解法, 执行用时: 436 ms, 内存消耗: 78.9 MB, 提交时间: 2023-09-24 23:04:28

/**
 * @param {number[][]} points
 * @param {number} angle
 * @param {number[]} location
 * @return {number}
 */
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;
}


// 滑动窗口
var visiblePoints2 = 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;
};

golang 解法, 执行用时: 296 ms, 内存消耗: 23.2 MB, 提交时间: 2023-09-24 23:03:54

// 滑动窗口
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
}

// 二分查找
func visiblePoints2(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
}

python3 解法, 执行用时: 416 ms, 内存消耗: 44.5 MB, 提交时间: 2023-09-24 22:58:59

class Solution:
    # 数学问题
    def visiblePoints1(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
        
    # 二分查找
    def visiblePoints2(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
        
    # 滑动窗口
    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