e-olymp 8357. Точка в многоугольнике

Задача

Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

Входные данные

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

Входные данные Выходные данные
3 0 0

1 0

0 1

1 1

NO
4 3 2

0 0

1 5

5 5

6 0

YES
3 5 6

2 3

8 0

-1 -3

NO
4 -2 3

0 0

5 0

0 6

3 3

 

NO
5 3 1

9 2

3 0

-2 -4

-4 0

-4 5

 

YES

Код программы

 

Решение

Задача сводится к поиску площадей:

1)Считаю площадь многоугольника векторным произведением.

2) Считаю площади всех треугольников, которые образуются всеми двумя соседними точками многоугольника и точкой, нахождение которой я проверяю.

3) Суммируем площади.

4)Если сумма равна настоящей площади, то точка внутри многоугольника, нет — снаружи.

Ссылки

e-olymp

ideone

 

One thought on “e-olymp 8357. Точка в многоугольнике

    • Не нужно делать список в ручную. У Вас есть кнопки и теги OL (ordered list) для организации списка и LI (list item).
    • Случай когда треугольники из п.2 не лежат целиком внутри многоугольника, нуждается в пояснении.
    • И самое «страшное» — задача на потоки. Нужно попытаться решить без массивов.

Добавить комментарий