|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.05.2019, 11:55 | #1 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Сколько из заданных точек принадлежит данному звездному многоугольнику
Здравствуйте.
Сижу над этой проблемой уже неделю и никак не могу решить. Пожалуйста помогите. Суть проблемы: Задача:Радиальный многоугольник Мы будем называть многоугольник, ограниченный многоугольником с ломаной прямой (то есть не пересекающимся), замкнутым с этим сломанным свойством, что внутри многоугольника есть точка (назовем ее фокусной точкой) с таким свойством, что отрезок, соединяющий эту точку с любой вершиной, полностью принадлежит этому многоугольнику. Задача состоит в том, чтобы решить, сколько из заданных точек принадлежит данному звездному многоугольнику. 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 Вот ещё есть рисунок для наглядного примера: Стрелки указывают расположение исследуемых точек. Красные стрелки указывают точки, принадлежащие радиальному многоугольнику. |
08.05.2019, 12:36 | #2 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
08.05.2019, 16:46 | #3 |
Форумчанин
Регистрация: 18.10.2009
Сообщений: 185
|
Один из вариантов реализации:
Из искомой точки проводите луч (например параллельно оси X). И считаете сколько рёбер этот луч пересекает. Если число пересечение нечётное, то точка принадлежит многоугольнику. (хотя тут конечно нужно очень аккуратно обращаться со случаями когда исходная точка находиться на ребре или вершине многоугольника, а также если одно из рёбер точно находиться на луче) Попытайтесь написать свой код, и тогда уже подумаем вместе над тонкостями реализации.
На С# пишу лучше чем на русском.
"У меня правильнописание хромает. Оно хорошее, но почему-то хромает." |
08.05.2019, 19:02 | #4 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
|
08.05.2019, 20:48 | #5 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Возможно)
|
10.05.2019, 16:53 | #6 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,318
|
Как вариант:
Используем свойство многоугольника: Цитата:
2. Вычисляем углы наклона лучей, проведённых из центра к этим вершинам (k1 и k2): коэффициент k уравнения y = kx. 3. Выбираем точку, принадлежность которой к многоугольнику надо проверить: пусть её координаты xp, yp. Если угол наклона луча, проведённого к точке, попадает в сектор (k1 < kp < k2), смотрим на положение точки относительно прямой AB (ищем в Гугл или Яндекс). Если точка слева от прямой, то её координаты в новый список, а если справа, то удаляем (полагаем, что координаты вершин многоугольника даны в направлении против часовой стрелки). Переставляем координаты вершин многоугольника (переходим к вершинам B и С) и просматриваем оставшиеся точки: повторяем с п.2. Каждый шаг уменьшает число рассматриваемых точек, а после просмотра всех вершин получим список точек, которые входят в многоугольник. PS: Надо рассматривать и случай, когда точки могут быть с x = 0. Возможно, что для таких точек достаточно систему координат повернуть на pi/2 (значения x и y меняются местами).
Как-то так, ...
|
|
11.05.2019, 21:45 | #7 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Сам алгоритм я понимаю как написать.
Я не понимаю соответствие Входа и Примера. Что за что отвечает. Подскажите пожалуйста. |
12.05.2019, 10:06 | #8 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,318
|
Из записанного тобой следует, что:
Код:
PS: За раскраску не отвечаю
Как-то так, ...
Последний раз редактировалось ViktorR; 12.05.2019 в 10:08. Причина: Изменение раскраски в сообщении |
12.05.2019, 10:07 | #9 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,318
|
За раскраску не отвечаю
Как-то так, ...
|
12.05.2019, 11:54 | #10 |
Пользователь
Регистрация: 08.05.2019
Сообщений: 27
|
Большое спасибо
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Определить количество заданных точек (x,y) | AlexMi64 | Lazarus, Free Pascal, CodeTyphon | 8 | 06.06.2018 09:06 |
Выделить из заданных точек вершины квадрата, содержащего максимальное число заданных точек | Kef1r | C# (си шарп) | 8 | 12.01.2017 16:00 |
Написать программу, которая определяет вершины квадрата содержащего макс. число заданных точек | Kef1r | Общие вопросы C/C++ | 16 | 12.01.2017 12:32 |
Даны три вещественных числа Если они принадлежат данному отрезку , то вывести их на печать в порядке возрастания. Если ни одно число не принадлежит отрезку, вывести сообщение об эт | Lushov | Помощь студентам | 0 | 02.12.2016 18:28 |
Среди N точек, заданных своими координатами на плоскости, определить самую дальнюю точку от начала координат. | zaira001002 | Общие вопросы C/C++ | 10 | 30.09.2013 10:26 |