Daily bit(e) of C++ | Visible points
Daily bit(e) of C++ #107, Common interview problem: Visible points
Given a list of points on a 2D plane, a location and an angle [0..360], return the maximum number of points that can be seen from the location using a field of vision with the width specified by the angle.
Points do not obstruct each other, including points that share the same position.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/6cvaosPMY.
Solution
Let’s first consider what we are trying to do here.
We want to iterate over sets of points where the angle between the “leftmost” and “rightmost” point is less (or equal) than the field of vision (our position is the origin).
The first step, therefore, will be calculating these angles. We can use std::atan2, which conveniently handles the corner cases where we would divide by zero (for points on the same x-coordinate). We get back the angle in radians.
Once we have all angles calculated and sorted, we only need to find a window in the data where the angle between the leftmost and rightmost element is less or equal to our field of vision and contains the maximum number of elements. We can do this using a sliding window.
There are a couple of corner cases we need to deal with.
we always see points we are standing on
our field of vision can span the end of the array of calculated angles, which we can fix by duplicating the array, adding 2*pi to each element
the duplication introduces another issue, where for a field of vision of 360 degrees, we double-count the elements with a minimal angle
Finally, we return the number of points we are standing on plus the size of the maximum window we found during our sliding window search.
