Вот изображение, и есть две линии, а именно y = 1 и y = 0, и некоторый отрезок, т. Е. (A1, B1) и A1 (m, 1) при y = 1 и B1 (n, 0) при y = 0. Некоторые сегменты пересекаются с другими сегментами, проблема заключается в том, чтобы разработать алгоритм для поиска числа пересечений на рисунке O (nlogn) . На рисунке 4 отрезка и 4 пересечения.
Вот моя мысль ----
Сначала , я мог бы сложить все отрезки линии и отсортировать их по значению x на y = 1, а затем рекурсивно разделить их, пока не останется только один отрезок.
Далее , я начинаю считать количество пересечений между моей левой частью и моей правой частью. возьмите A1 (m, 1) B1 (n, 0) и A2 (w, 1) B2 (v, 0), например, если w> m и v
Как только закончил проверку между (A1, B1) и (A2, B2) и (A3, B3) и (A4, B4), мне нужно получить номер пересечения левой части [( A1, B1), (A2, B2)] с правой частью [(A3, B3), (A4, B4)] и , где я застрял . Я уже знал номер пересечения между (A1, B1) и (A2, B2) и (A3, B3) и (A4, B4), как мне получить номер пересечения между элементом в правой части и элементом слева часть в O (n), так как общее время выполнения O (nlogn), поэтому для получения номера пересечения требуется O (n). Я не могу просто перебрать элементы справа, чтобы проверить номер пересечения со всеми элементами слева, который бы взял O (n ^ 2).
Любая помощь приветствуется. И если моя мысль пока не является правильной, пожалуйста, укажите это.