Show problems as
Classic problem #1610HardArrayMathGeometrySliding WindowSorting

Maximum Number of Visible Points

Real-world version: Aiming the Yard Camera
Tracked in this browser only
Read Maximum Number of Visible Points on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A stocktake camera sits on a fixed mast in a container yard. The yard is mapped on integer grid coordinates: the mast stands at mast = [mx, my], and tags lists the coordinates of the radio tags stuck to the containers, so tags[i] = [xi, yi]. Several tags may sit at the same coordinates, and a tag may sit at the mast's own coordinates.

The camera can be swivelled to any bearing but its lens is fixed: it takes in a wedge that is exactly sweep degrees wide, with the mast at the wedge's tip. Aim it once and it reads every tag that falls inside that wedge, edges included; a tag exactly on either edge is read. Containers do not hide one another, so distance and stacking are irrelevant. A tag lying at the mast's own coordinates has no bearing at all and is read no matter where the camera points.

Return the largest number of tags a single aim can read.

Examples

Example 1

Input
tags = [[6, 4], [7, 4], [8, 5]], sweep = 45, mast = [5, 4]
Output
3

Pointing the camera due east takes in all three tags at once, so nothing is left out of the reading.

Example 2

Input
tags = [[5, 4], [5, 4], [2, 8], [8, 8]], sweep = 0, mast = [5, 4]
Output
3

Two tags share the mast's coordinates and are read on any aim. The wedge has no width at all, so of the two remaining tags only one can be lined up.

Example 3

Input
tags = [[44, 51], [44, 49], [46, 52]], sweep = 40, mast = [50, 50]
Output
3

One aim towards the west, tilted slightly north, brings all three tags inside the wedge together.

Constraints

  • 1 <= tags.length <= 10^5
  • tags[i].length == 2
  • mast.length == 2
  • 0 <= sweep < 360
  • 0 <= mx, my, xi, yi <= 100
  • The answer is a plain tag count, so no rounding is involved.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tags_in_view(tags: list[list[int]], sweep: int, mast: list[int]) -> int:
Java
public int tagsInView(int[][] tags, int sweep, int[] mast)

More on the same topics