Ctrl K

Меньше всего прямых через точки

Средняя
На клетчатой бумаге отмечены точки dots, где dots[i] = [x, y] — координаты i-й точки. Все точки различны. Нужно провести несколько прямых линий (бесконечных в обе стороны) так, чтобы каждая точка лежала хотя бы на одной из них. Верните наименьшее число прямых, которого для этого хватит.
Пример 1
dots=[[0, 0], [1, 1], [2, 2], [0, 2], [2, 0]] → 2

Одна прямая проходит через [0, 0], [1, 1], [2, 2], вторая — через [0, 2] и [2, 0]. Все пять точек на одной прямой не лежат, поэтому меньше двух нельзя.

Пример 2
dots=[[3, -1]] → 1

Через одну точку достаточно провести одну прямую.

Пример 3
dots=[[0, 0], [1, 2], [2, 4], [3, 6]] → 1
Ограничения
  • 1 ≤ len(dots) ≤ 10
  • dots[i] состоит из двух чисел
  • -100 ≤ x, y ≤ 100
  • Все точки различны
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЦепочки с квадратными суммами СложнаяКвадратная рамка из палочек СредняяРассадка с делимостью СредняяСамая дешёвая корзина с наборами СредняяГруппы с равными суммами Средняя
загружаем Python…
Вход
dots=[[0, 0], [1, 1], [2, 2], [0, 2], [2, 0]]
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 97 тестов на сервере, включая скрытые.