minimum-number-of-lines-to-cover-points

< Previous 　　　　　　　　　　　　　　　　 Next >

2152. Minimum Number of Lines to Cover Points (Medium)

Related Topics

[Bit Manipulation] [Geometry] [Array] [Hash Table] [Math] [Dynamic Programming] [Backtracking] [Bitmask]

Hints

Hint 1

What is the highest possible answer for a set of n points?

Hint 2

The highest possible answer is n / 2 (rounded up). This is because you can cover at least two points with a line, and if n is odd, you need to add one extra line to cover the last point.

Hint 3

Suppose you have a line covering two points, how can you quickly check if a third point is also covered by that line?

Hint 4

Calculate the slope from the first point to the second point. If the slope from the first point to the third point is the same, then it is also covered by that line.