Если коротко: ребята, скажите, где можно студентам "почитать про сканирующая прямую"?
Мне интересны не решения геометрических задач по типу "найти два пересекающихся отрезка на плоскости" (которые как раз даже в wiki разобраны), а применение сканирующей прямой к структурам данных. Например, пусть на плоскости даны прямоугольники со сторонами параллельными осям координат и точки, нужно посчитать для каждого прямоугольника, сколько точек внутри? Самое простое решение за -- сканирующая прямая с деревом Фенвика.
bump