Сколько из заданных точек принадлежит данному звездному многоугольнику

[Programist_r]

Здравствуйте.
Сижу над этой проблемой уже неделю и никак не могу решить. Пожалуйста помогите.

Суть проблемы:

Задача:Радиальный многоугольник

Мы будем называть многоугольник, ограниченный многоугольником с ломаной прямой (то есть не пересекающимся), замкнутым с этим сломанным свойством, что внутри многоугольника есть точка (назовем ее фокусной точкой) с таким свойством, что отрезок, соединяющий эту точку с любой вершиной, полностью принадлежит этому многоугольнику. Задача состоит в том, чтобы решить, сколько из заданных точек принадлежит данному звездному многоугольнику.

1. читает из стандартного ввода описание радиального многоугольника, заданного координатами его вершин и координатами исследуемых точек;
2. вычисляет, сколько точек он рассматривает, принадлежит радиальному многоугольнику и записывает результат в стандартный вывод.

Вход:
В первой строке стандартного ввода дается натуральное число C (C ≈ 15). Следующие строки содержат наборы данных C, которые хранятся в соответствии со спецификацией, приведенной ниже.
Один набор данных в первой строке содержит два целых числа n и m, разделенных одним пробелом, обозначающих количество вершин радиального многоугольника и количество точек, принадлежность которых к многоугольнику должна быть проверена (3 ≤ n ≤ 100000, 0 ≤ m ≤ 100000).
В строках 2 ... (n + 1) n заданы целочисленные координаты вершин xi, yi, разделенных одним пробелом. Они даны в том порядке, в котором они встречаются, когда многоугольник обходится против часовой стрелки (xi, yi  [-32000; 32000]). Центральная точка каждого центрального многоугольника является источником системы координат, то есть точкой с координатами (0, 0).
В строках (n + 2) ... (m + n + 1) целые числа ui, vi точек, принадлежность которых к радиальному многоугольнику должна быть проверена (ui, vi  [-32000; 32000]), разделены одним пробелом.

Выход:
В следующих строках стандартного вывода программа должна предоставить ответы, рассчитанные для последующих наборов данных.
Результатом для одного набора данных является одно целое число, обозначающее количество точек, принадлежащих многоугольнику, определенному в данном наборе.

ПРИМЕР:
Вход:

2
4 2
-2 -2
0 4
1 1
4 0
2 2
-1 1
6 5
2 2
4 4
6 6
-3 1
-1 -1
5 1
2 1
3 2
6 6
3 3
-3 0

ОТВЕТ:
1
3


Вот ещё есть рисунок для наглядного примера:

Стрелки указывают расположение исследуемых точек.

Красные стрелки указывают точки, принадлежащие радиальному многоугольнику.

[Аватар]

Сижу над этой проблемой уже неделю и никак не могу решить

Метод трассировки луча

[val_nnm]

Один из вариантов реализации:
Из искомой точки проводите луч (например параллельно оси X). И считаете сколько рёбер этот луч пересекает. Если число пересечение нечётное, то точка принадлежит многоугольнику. (хотя тут конечно нужно очень аккуратно обращаться со случаями когда исходная точка находиться на ребре или вершине многоугольника, а также если одно из рёбер точно находиться на луче)
Попытайтесь написать свой код, и тогда уже подумаем вместе над тонкостями реализации.

[Black Fregat]

Сообщение от Programist_r

ограниченный многоугольником с ломаной прямой (то есть не пересекающимся), замкнутым с этим сломанным свойством

Это что, маш. перевод? Оригинал бы..

[Programist_r]

Возможно)

[ViktorR]

Как вариант:
Используем свойство многоугольника:

... внутри многоугольника есть точка (назовем ее фокусной точкой) с таким свойством, что отрезок, соединяющий эту точку с любой вершиной, полностью принадлежит этому многоугольнику ...

1. Берём две вершины многоугольника: пусть это A и B.
2. Вычисляем углы наклона лучей, проведённых из центра к этим вершинам (k1 и k2): коэффициент k уравнения y = kx.
3. Выбираем точку, принадлежность которой к многоугольнику надо проверить: пусть её координаты xp, yp.
Если угол наклона луча, проведённого к точке, попадает в сектор (k1 < kp < k2), смотрим на положение точки относительно прямой AB (ищем в Гугл или Яндекс). Если точка слева от прямой, то её координаты в новый список, а если справа, то удаляем (полагаем, что координаты вершин многоугольника даны в направлении против часовой стрелки).
Переставляем координаты вершин многоугольника (переходим к вершинам B и С) и просматриваем оставшиеся точки: повторяем с п.2.
Каждый шаг уменьшает число рассматриваемых точек, а после просмотра всех вершин получим список точек, которые входят в многоугольник.

PS: Надо рассматривать и случай, когда точки могут быть с x = 0.
Возможно, что для таких точек достаточно систему координат повернуть на pi/2 (значения x и y меняются местами).

[Programist_r]

Сам алгоритм я понимаю как написать.
Я не понимаю соответствие Входа и Примера. Что за что отвечает. Подскажите пожалуйста.

[ViktorR]

Из записанного тобой следует, что:

 2       - число рассматриваемых многоугольников
 4  2    - число вершин первого многоугольника и число тестируемых точек
-2 -2    - первая вершина многоугольника
 0  4    -
 1  1    -
 4  0    - четвёртая вершина многоугольника
 2  2    - первая тестируемая точка
-1  1    - вторая тестируемая точка
 6  5    - число вершин второго многоугольника и число тестируемых точек
 2  2    - первая вершина многоугольника
 4  4    -
 6  6    -
-3  1    -
-1 -1    -
 5  1    - шестая вершина многоугольника
 2  1    - первая тестируемая точка
 3  2    - вторая тестируемая точка
 6  6    -
 3  3    -
-3  0    - пятая тестируемая точка.

Так понятней?

PS: За раскраску не отвечаю

[ViktorR]

За раскраску не отвечаю

[Programist_r]

Большое спасибо