Editor

Most Landmarks in View

#468 · Geometry · Expert · 240 XP · about 50 min

You stand at location, an (x, y) tuple, and there are landmarks at points, a list of (x, y) tuples (all integers). You cannot walk, but you can turn on the spot to face any direction. Your field of view is a slice of the plane angle degrees wide with you at its tip: facing direction d, you see every landmark whose direction from you is at most angle / 2 degrees away from d on either side, edges included. Landmarks never block each other.

A landmark at your own position is always visible, whichever way you face.

Write most_visible(points, angle, location) that returns the largest number of landmarks you can see at the same time.

Examples

most_visible([(3, 1), (2, 2), (1, 3), (-2, 0)], 60, (0, 0))    # returns 3
most_visible([(1, 1), (-1, -1), (0, 0), (5, 5)], 90, (0, 0))   # returns 3
most_visible([(1, 0), (0, 1), (-1, 0), (0, -1)], 360, (0, 0))  # returns 4

In the first example the directions to the first three landmarks are about 18, 45 and 72 degrees, which fit in a 60 degree view; (-2, 0) is behind you. In the second, (1, 1) and (5, 5) lie in the same direction, and (0, 0) is where you stand, so you see three.

Constraints

  • 1 to 100,000 landmarks; the same position can appear more than once, and each one counts.
  • Coordinates are between -10,000 and 10,000.
  • angle is a whole number from 1 to 360.
  • In every test, making angle a millionth of a degree wider or narrower would not change the answer, so tiny rounding errors in computed angles cannot change your result.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.