Количество пересекающихся линий, образованных из каждой возможной пары заданных точек

Даны два массива целых чисел, X и Y, представляющие точки на плоскости XY. Подсчитайте количество пересекающихся пар отрезков, образованных каждой возможной парой координат.

Example:

Input: X = [0, 1, 0, 1], Y = [0, 1, 3, 2]

Output: 14

Explanation:

For simplicity let’s denote A = [0, 0], B = [1, 1], C = [1, 2], D = [0, 3].

1. Line segment between point (A, B) and point (A, C) intersects.
2. Line segment between point (A, B) and point (A, D) intersects.
3. Line segment between point (A, B) and point (B, D) intersects.
4. Line segment between point (A, B) and point (C, D) intersects.
5. Line segment between point (A, B) and point (B, C) intersects.
6. Line segment between point (A, C) and point (C, D) intersects.
7. Line segment between point (A, C) and point (B, D) intersects
8. Line segment between point (A, C) and point (A, D) intersects.
9. Line segment between point (A, C) and point (B, C) intersects..
10. Line segment between point (A, D) and point (B, D) intersects.
11. Line segment between point (A, D) and point (C, D) intersects.
12. Line segment between point (B, C) and point (B, D) intersects.
13. Line segment between point (B, C) and point (C, D) intersects.
14. Line segment between point (B, D) and point (C, D) intersects.

Input: X = [0, 0, 0, 2], Y = [0, 2, 4, 0]

Output: 6

Наивный подход:

1. Храните все пары координат в структуре данных.
2. Для каждой пары пар координат проверьте, параллельны они или нет. Если они не параллельны, то эта линия должна пересечься. Увеличьте ответ на 1.

Временная сложность: O(N^4)

Эффективный подход:

1. Для каждой пары координат сохраните эти параметры (наклон, пересечение по оси x или оси y) линии.
2. Для линий, параллельных оси X:
   • Наклон = 0, точка пересечения = Y[i]
3. Для линий, параллельных оси Y:
   • Наклон = INF, точка пересечения = X[i]
4. Для всех остальных строк:
   • Наклон = (dy/dx = (y2 – y1)/(x2 – x1)
   • Чтобы вычислить точку пересечения, мы знаем общую форму линии, т.е. y = (dy/dx)*x + c
     • Поместив y1 вместо y и x1 вместо x, поскольку сама линия проходит через (x1, y1).
     • После вышеуказанного шага мы получаем Intercept = (y1*dx – x1*dy)/dx.
5. Тогда для каждой строки у нас есть три случая:
   • Линия может иметь тот же наклон и точку пересечения, что и другая линия. Эти линии не будут пересекаться, так как они в основном являются одной и той же линией.
   • Линия может иметь такой же наклон и разные точки пересечения с какой-либо другой линией. Эти линии также не будут пересекаться, так как они параллельны.
   • Линия может иметь наклон, отличный от какой-либо другой линии. Эти линии обязательно пересекутся независимо от точек их пересечения .
6. Сохраните частоту линий с одинаковым уклоном. Сохраните карту в соответствии с указанными выше условиями, зафиксируйте тип сегмента линии и рассчитайте количество пересекающихся сегментов линии с оставшимися линиями.

Примечание:

В приведенной ниже реализации мы избегали использования двойников, чтобы избежать ошибок, вызванных ошибками точности.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*N*logN)

Космическая сложность: O(N)