170
правок
Изменения
Нет описания правки
Рассмотрим этот прямоугольник.
На момент <tex>i</tex>-го запроса рассмотрим в дереве поиска наименьшего общего предка <tex>x</tex> и <tex>y</tex> -- вершину <tex>t</tex>.
Если <tex>t != x</tex>, то все хорошо, значит в дереве поиска она находится между <tex>х</tex> и <tex>у</tex>, поэтому мы к нему обращались в то время, когда шли к <tex>хx</tex>, значит есть точка на стороне нашего многоугольника.
(Рис.2)
Если <tex>t = x</tex>, то есть <tex>хx</tex> -- предок <tex>уy</tex> в момент <tex>i</tex>-го запроса,
тогда рассмотрим момент <tex>j</tex>-го запроса, когда мы обращались к <tex>y</tex>.
Найдем в дереве поиска наименьшего общего предка <tex>t</tex> вершин <tex>x</tex> и <tex>y</tex> на момент <tex>j</tex>-го запроса.
