All problems

Max Points on a Line

Hard · math

A treasure map shows n marked spots. You are given them as points, where points[i] = [x, y] are the coordinates of spot i. No two spots are in the same place.

Lay a single straight rod across the map, at any angle (flat, upright or slanted). Every spot the rod touches exactly is covered.

Return the largest number of spots a single rod can cover.

Examples

Example 1

Input: points = [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]

Output: 4

The spots (1, 4), (2, 3), (3, 2) and (4, 1) all sit on one slanted line. No line covers more.

Example 2

Input: points = [[2, 1], [2, 5], [2, 9], [6, 9]]

Output: 3

Three spots share x = 2, so an upright rod covers them.

Example 3

Input: points = [[5, 5], [9, -3]]

Output: 2

Any two spots can always be covered by one rod.

Constraints