Почему это работает
- Две прямые через одну точку p с одинаковым наклоном — это одна прямая. Значит, точки после p с общим наклоном лежат на одной прямой с p, и словарь их считает.
- Наклон храним сокращённой дробью dy/dx, а не результатом деления: 4/2 и 2/1 дают один ключ, нет ошибок округления, а вертикальная прямая — просто 1/0.
- Прямая через более раннюю точку уже посчитана, когда та была p, поэтому каждая p смотрит только на точки после себя.
Сложность
Время O(n²): каждую пару точек смотрим один раз (сокращение дроби добавляет короткий НОД). Память O(n): в словаре не больше n − 1 наклонов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗