Maximum Number of Visible Points

This is an optimized approach that avoids the O(N^2) complexity. It involves calculating the angle for each point, sorting these angles, and then using a sliding window technique to find the maximum number of points that can fit within the given angle range. The circular nature of angles is handled by duplicating the angle list.

• 1. Separate points at the observer's location from other points. Count them in pointsAtLocation.
• 2. For each point not at the location, calculate its angle relative to the observer using Math.atan2, convert to degrees, and normalize to [0, 360).
• 3. Store these angles in a list.
• 4. Sort the list of angles in ascending order.
• 5. To handle the circular nature of angles, create a new extended list. This list contains the original sorted angles followed by a copy of each angle with 360 added to it.
• 6. Initialize two pointers, start = 0 and end = 0, for the sliding window, and maxPoints = 0.
• 7. Iterate with the end pointer from the beginning to the end of the extended list.
• 8. Inside the loop, move the start pointer forward as long as the angular distance between the points at end and start is greater than the given angle (angles.get(end) - angles.get(start) > angle).
• 9. The current number of points in the window is end - start + 1. Update maxPoints = max(maxPoints, end - start + 1).
• 10. After the loop, the final answer is maxPoints + pointsAtLocation.

Similar to the first approach, we first handle points at the observer's location and calculate the angles for all other points, normalizing them to [0, 360). The key insight is that if we sort the angles, we can efficiently find the number of points in any given angular range.

The problem is on a circle, so a view window might "wrap around" from 360 to 0 degrees (e.g., from 350 to 20 degrees). To handle this easily, we create an extended list of angles. We take our sorted list of angles a1, a2, ..., aN and append a second copy of each angle incremented by 360: a1+360, a2+360, ..., aN+360. This transforms the circular problem into a linear one.

Now, we can apply a sliding window (two-pointer) approach on this new, extended list. We use a start pointer and an end pointer, both initialized to the beginning. We iterate the end pointer through the extended list. For each position of end, we advance the start pointer until the angle at start is within the allowed angle degrees from the angle at end (i.e., angles.get(end) - angles.get(start) <= angle). The number of points in the current valid window is end - start + 1. We keep track of the maximum window size found. This maximum size is the maximum number of points visible in any single rotation. We add the count of points at the observer's location to get the final answer.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        List<Double> angles = new ArrayList<>();
        int pointsAtLocation = 0;
        int locX = location.get(0);
        int locY = location.get(1);

        for (List<Integer> p : points) {
            int pX = p.get(0);
            int pY = p.get(1);
            if (pX == locX && pY == locY) {
                pointsAtLocation++;
            } else {
                angles.add(calculateAngle(locY, locX, pY, pX));
            }
        }

        Collections.sort(angles);

        // To handle wrap-around, duplicate the angles array with +360
        List<Double> circularAngles = new ArrayList<>(angles);
        for (double ang : angles) {
            circularAngles.add(ang + 360.0);
        }

        int maxPoints = 0;
        if (angles.isEmpty()) {
            return pointsAtLocation;
        }

        int start = 0;
        for (int end = 0; end < circularAngles.size(); end++) {
            while (circularAngles.get(end) - circularAngles.get(start) > angle) {
                start++;
            }
            maxPoints = Math.max(maxPoints, end - start + 1);
        }

        return maxPoints + pointsAtLocation;
    }

    private double calculateAngle(int y1, int x1, int y2, int x2) {
        double angleRad = Math.atan2(y2 - y1, x2 - x1);
        double angleDeg = Math.toDegrees(angleRad);
        if (angleDeg < 0) {
            angleDeg += 360;
        }
        return angleDeg;
    }
}