Есть такая классическая задача: дано N вершин многоугольника и K точек. Проверить для каждой точки, лежит ли она внутри многоугольника. Многоугольник может быть любым. Алгоритмы, представленные здесь и здесьYour text to link here... содержат лишь пару слов о том, что при использовании деревьев в предпроцессинге ответ на запрос можно сделать logN. Сам алгоритм я понимаю как нахождение количеств пересечений луча, направленного строго вправо из нашей точки. Для нахождения такого количества мне нужно знать количество отрезков, начало которых выше луча, а конец ниже или наоборот. а также количество отрезков где ровно одна вершина лежит на луче.

Однако я совсем не понимаю, где здесь приткнуть деревья для предпосчета, чтобы потом быстро находить количество пересечений. Можете подсказать, как это здесь применимо?