Fewest Lines Through the Dots

Medium

Some dots are marked on graph paper: dots[i] = [x, y] gives the coordinates of the i-th dot. All dots are distinct. You need to draw straight lines (infinite in both directions) so that every dot lies on at least one of them. Return the smallest number of lines that does the job.

Example 1

dots=[[0, 0], [1, 1], [2, 2], [0, 2], [2, 0]] → 2

One line goes through [0, 0], [1, 1], [2, 2] and another through [0, 2] and [2, 0]. The five dots are not all on one line, so fewer than two is impossible.

Example 2

dots=[[3, -1]] → 1

A single dot needs just one line.

Example 3

dots=[[0, 0], [1, 2], [2, 4], [3, 6]] → 1

Constraints

1 ≤ len(dots) ≤ 10
Each dots[i] holds two numbers
-100 ≤ x, y ≤ 100
All dots are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Geometry Array Hash Table Math Dynamic Programming Backtracking Bitmask

Similar problems

Square-Sum Chains Hard Square Frame From Sticks Medium Seating by Divisibility Medium Cheapest Basket with Bundles Medium Groups With Equal Sums Medium

Input

dots=[[0, 0], [1, 1], [2, 2], [0, 2], [2, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.