Московская олимпиада по информатике - 2005: различия между версиями

'''Ориентированной площадью''' ('''A''', '''B''') пары векторов '''A''' = (x1, y1) и '''B''' = (x2, y2) назовем число, равное x1*y2 − y1*x2. По абсолютно величине она равна площади параллелограмма, у которого в качестве сторон взяты '''A''' и '''B''', отложенные от одной точки. Она равна нулю тогда и только тогда, когда '''A''' и '''B''' коллинеарны. В противном случае знак ('''A''', '''B''') дает нам информацию о направлении кратчайшего поворота от вектора '''A''' к вектору '''B'''.

Если система координат выбрана стандартным образом, то ('''A''', '''B''') больше нуля тогда и только тогда, когда кратчайший поворот – против часовой стрелки, см.рис.1 (соответственно, ('''A''', '''B''') меньше нуля тогда и только тогда, когда кратчайший поворот – по часовой стрелке, см. рис. 2).

 

Назовем '''началом''' отрезка XY ту его вершину, которая встретится при вращении нашей прямой раньше остальных точек этого отрезка; '''концом''' – ту, которая встретится последней. Это можно определить, вычислив знак ориентированной площади S = ('''PX''', '''PY'''): если X – начало, то S > 0. В случае, если X, Y и P лежат на одной прямой, началом будем считать любую из вершин, концом – оставшуюся.

 

Пусть отрезок XY после возможной симметрии его вершин, описанной выше, перешел в отрезок X'Y'. Если ориентированная площадь ('''PX''', '''PY''') отличается по знаку от ориентированной площади ('''PX'''', '''PY''''), то визуально начало и конец «поменялись местами» (мы по-прежнему называем X` началом, если X – начало и наоборот – концом, если X - конец). То есть при вращении наша прямая сначала встретит конец X`Y`, а потом начало (см. рис. 3). В этом случае надо учитывать, что прямые из области 3 (см. рис. 3) тоже пересекают XY (в алгоритме – шаг 3). Кстати, такое возможно, только если XY – первого типа.

 

С отрезками второго типа таких неудобств не будет.