# по обе стороны от

по обе стороны от точки A на прямой окажется четное число точек пересечения со сторонами, то точка лежит вне многоугольника, а если нечетное - то внутри. Таким образом, алгоритм состоит в следующем: выбираем прямую, находим, с какими сторонами она пересекается и в каких точках, и считаем количество таких точек с одной стороны от A. В качестве прямой удобно взять, например, горизонтальную прямую (Y = A.y). Для нее проще, чем для произвольной прямой, проверять наличие точки пересечения с отрезком, считать ее координату (одну!) и проверять, с какой стороны от A эта точка лежит. При реализации этого алгоритма стоит иметь в виду 2 небольшие детали: * прямая может проходить через вершину многоугольника, причем 2 разными способами - пересекая границу многоугольника или касаясь границы многоугольника; * сторона прямоугольника может быть горизонтальной и лежать на прямой. Время O(N) является неплохим, и вряд ли можно желать лучшего, если речь идет о вопросе, решаемом

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа