какие из секторов входят данные 10 точек? разбиение состоит из невыпуклых и выпуклых многоугольников. нужно будет повторить операцию проверки вхождения много раз
cчитать что косое произведение (псево-скаляр, знаковая площадь)? но это вроде только для выпуклых
Если про асимптотику говорить, то режешь на (условно) вертикальные полосы (внутри полосы нет точек разбиения). Строишь для каждой полосы дерево поиска. А ещё, чтоб не строить с нуля деревья для всех полос (независимо), можешь строить персистентное красно-черное дерево, передвигаячь по полосам. На практике же стоит посмотреть в сторону kd-деревьев и их модификаций.
Обсуждают сегодня