Member 14773225 Ответов: 1

Количество пересечений отрезков линии ?

You are given N points in a plane (numbered 1 through N); for each valid i, the i-th point is Pi=(i,Ai). There are N−1 line segments between them (numbered 1 through N−1); for each valid i, the i-th line segment is formed by connecting the points Pi and Pi+1.

You are given Q horizontal line segments . Each query horizontal line segment is denoted by two points, from a point (x1,y) to a point (x2,y) (where it stops and does not propagate further). For Every Horizontal line segment, you have to find the number of line segments from those (N-1 line segments) it collides with on the way.

So this is the problem where :
2<=N<= 100000
!<=Q<= 100000

Can anyone teach me what approach will be best and most effective in terms of time complexity?


Что я уже пробовал:

Я не знаю, как к этому подступиться .Я подумал, что дерево КД может помочь.Но я не знаю, как использовать его для линейного сегмента.

1 Ответов

Рейтинг:
1

Patrice T

Цитата:
Может ли кто-нибудь научить меня, какой подход будет лучшим и наиболее эффективным с точки зрения временной сложности?

Подход-это грубая сила, тест очень одного сегмента против каждого горизонтального сегмента.
Применить метод поцелуй список из N-1 отрезков, список м горизонтальные отрезки, ничего особенного.
Сложность равна (N-1)*Q
Цитата:
Я подумал, что дерево КД может помочь.

Чтобы использовать метод с тем или с другим, вам нужно иметь представление о том, как он поможет раньше.
Когда вы ищете правильный алгоритм для решения проблемы:
- сначала выберите грубую силу и оцените рабочую нагрузку.
- Поиск улучшенного метода и оценка новой рабочей нагрузки, сохранение, если снижение рабочей нагрузки.
- попробуйте улучшить дальше с помощью другого метода или уточнения.