Форум программистов, компьютерный форум CyberForum.ru

Окружение точки - C++

Восстановить пароль Регистрация
 
yanyk1n
 Аватар для yanyk1n
4324 / 1455 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
18.12.2010, 22:00     Окружение точки #1
Всем читающим эту тему доброго времени суток! Хоть сам я учусь на программиста, не обходится без трудностей. Вот одна из них:

Описание: На плоскости даны точки A1, A2, ..., AN и точка B, никакие две точки не совпадают.
Найдите многоугольник минимального периметра с вершинами в точках Ai, содержащий точку B. Стороны многоугольника должны быть меньше либо равны K. Некоторые из точек Ai могут быть не задействованны.

Вход: В первой строке записано натуральное число N, 3 <= N <= 100, и вещественное число K - максимальная длина куска верёвки, 0 <= K <= 30000.
В следующей строке дана пара координат точки B. Далее записаны N пар координат (Xi, Yi) точек Ai.
Координаты и число K заданы с 4 знаками после запятой. Координаты по модулю не превосходят 10000.

Выход: Минимальная длина периметра с точностью два знака после запятой.

Добавлено через 23 минуты
Идея моего семинариста: перевести все точки в полярные координаты, а точку B выбрать как начало координат. Но до реализации алгоритма дело не дошло...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.12.2010, 00:16     Окружение точки #2
Первое, что приходит в голову -- отсортировать массив из точек по удаленности от точки B и взять из него K ближайших (к B).
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 01:01     Окружение точки #3
Первое, что приходит в голову, полный граф:
1) исключить ребра, не удовлетворяющие условие длинны. (Исключить изолированные вершины)
2) найти цыкл Гамильтона с минимальной суммой весов ребер(алгоритмов готовых хоть отбавляй).
yanyk1n
 Аватар для yanyk1n
4324 / 1455 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 01:25  [ТС]     Окружение точки #4
Manjak, не каждый Гамильтонов цикл не будет являться выпуклым многоугольником.
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 01:28     Окружение точки #5
О выпуклом многоугольнике в задании речи не было.
yanyk1n
 Аватар для yanyk1n
4324 / 1455 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 01:33  [ТС]     Окружение точки #6
Manjak, ах да, это уже было усложнение задачи, вне условий... Но всё равно надо каким-то образом проверять принадлежность точки этому многоугольника.
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 02:02     Окружение точки #7
Можно по другому, тоже в лоб:
найти покрывающее дерево, замкнуть оптимальми сторонами, исключить возможные циклы.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 08:49     Окружение точки #8
yanyk1n, Ссылку на тестирующую систему можете дать?
yanyk1n
 Аватар для yanyk1n
4324 / 1455 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 13:18  [ТС]     Окружение точки #9
valeriikozlov, http://acm.mipt.ru/judge/problems.pl?&problem=120
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2010, 09:18     Окружение точки
Еще ссылки по теме:

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников C++
Переделать из консоли в VCL Forms (поиск оптимальных путей от точки А до точки Б) C++ Builder
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.12.2010, 09:18     Окружение точки #10
1
Стороны многоугольника должны быть меньше либо равны K.
2
Минимальная длина периметра
второе не противоречит первому ?

вроде треугольник найти надо
Yandex
Объявления
20.12.2010, 09:18     Окружение точки
Ответ Создать тему
Опции темы

Текущее время: 02:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru