TUZ_2-27 Поиск прямой в двумерной сетке, пересекающей наибольшее количество точек
Точка в двумерной целочисленной сетке представлена кортежем с координатами x и y, например (2, 5) или (10, 3).
Через две разные точки на плоскости проходит ровно одна прямая. Эта прямая простирается бесконечно по обе стороны и пересекает бесконечное число других точек на плоскости. Доказать это утверждение не просто, но оно верное, поэтому примем его за аксиому.
Ваша задача: написать функцию, которая принимает список точек в двумерной сетке и отыскивает прямую, заданную двумя точками, которая пересекает наибольшее количество точек из заданного списка. Функция должна возвращать не саму прямую, а только количество точек, лежащих на ней.
В табл. 2.27 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.27. Некоторые ожидаемые результаты для задачи поиска прямой, пересекающей наибольшее количество из заданных точек |
| k |
Ожидаемый результат |
| (4, 4), (6, 6), (3, 2), (1, 4) |
2 |
| (14, 4), (0, 0), (1, 2), (3, 0) |
2 |
| (3, 15), (1, 4), (2, 6), (8, 7), (3, 8) |
3 |