Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
yanyk1n
4330 / 1461 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
#1

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

18.12.2010, 22:00. Просмотров 929. Ответов 9
Метки нет (Все метки)

Всем читающим эту тему доброго времени суток! Хоть сам я учусь на программиста, не обходится без трудностей. Вот одна из них:

Описание: На плоскости даны точки 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 выбрать как начало координат. Но до реализации алгоритма дело не дошло...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2010, 22:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Окружение точки (C++):

собрать программу. окружение графа. - C++
в течении двух недель нужно написать курсовую, помогите пожалуйста. Задание: Граф задаётся своей матрицей смежности, вывести на экран...

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество сделанных замен.

Во введенной строке заменить все запятые на точки, а точки - на восклицательные знаки - C++
15. В введенной строке заменить все запятые на точки, а точки - на восклицательные знаки. Подсчитать количество таких замен. почему оно...

Как найти координаты точки на прямой удаленной от заданной точки на х - C++
Добрый день! Помогите мне пожалуйста со следующей задачей. Дано 3 точки с координатами A(x1,y1), B(x2,y2), C(x3,y3) Нужно найти...

Массив, заполненный 1 и 0. Найти путь, состоящий из нулей, от точки до точки. - C++
Доброго времени суток всем! Вот такая задача, ничего не могу даже сообразить по ней, подкиньте идеи, пожалуйста (ну или код в C++ )

Найти точки пересечения прямых проходящих через заданные точки - C++
Всем привет! Прошу помощи в решении задачи: Дана система координат X:Y (по 25 точек в каждую сторону) В ней расположен ряд точек в...

9
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
19.12.2010, 00:16 #2
Первое, что приходит в голову -- отсортировать массив из точек по удаленности от точки B и взять из него K ближайших (к B).
0
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 01:01 #3
Первое, что приходит в голову, полный граф:
1) исключить ребра, не удовлетворяющие условие длинны. (Исключить изолированные вершины)
2) найти цыкл Гамильтона с минимальной суммой весов ребер(алгоритмов готовых хоть отбавляй).
0
yanyk1n
4330 / 1461 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 01:25  [ТС] #4
Manjak, не каждый Гамильтонов цикл не будет являться выпуклым многоугольником.
0
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 01:28 #5
О выпуклом многоугольнике в задании речи не было.
0
yanyk1n
4330 / 1461 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 01:33  [ТС] #6
Manjak, ах да, это уже было усложнение задачи, вне условий... Но всё равно надо каким-то образом проверять принадлежность точки этому многоугольника.
0
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
19.12.2010, 02:02 #7
Можно по другому, тоже в лоб:
найти покрывающее дерево, замкнуть оптимальми сторонами, исключить возможные циклы.
0
valeriikozlov
Эксперт С++
4672 / 2498 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2010, 08:49 #8
yanyk1n, Ссылку на тестирующую систему можете дать?
1
yanyk1n
4330 / 1461 / 152
Регистрация: 12.03.2009
Сообщений: 5,310
19.12.2010, 13:18  [ТС] #9
valeriikozlov, http://acm.mipt.ru/judge/problems.pl?&problem=120
0
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
20.12.2010, 09:18 #10
1
Стороны многоугольника должны быть меньше либо равны K.
2
Минимальная длина периметра
второе не противоречит первому ?

вроде треугольник найти надо
0
20.12.2010, 09:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2010, 09:18
Привет! Вот еще темы с ответами:

В символьной строке вместо каждой точки вставить три точки - C++
В символьной строке типа char, вводимой с клавиатуры вместо каждой найденной точки вставить три точки Желательно использовать только...

Вывести расстояние от заданной точки до точки пересечения диагоналей прямоугольников - C++
Прямоугольники заданы координатами их вершин. 1)Вывести расстояние от заданной точки до точки пересечения диагоналей. 2) Вывести...

Найти координаты самой низкой точки траектории и другой наивысшей точки подъема - C++
помогите решить пожуйста очень надо...не используя некакие циклы и ветвленее..они тока на алгоритмы линейные задачки 1.Заданы...

Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;time.h&gt; #define B 100 using namespace std; void gen...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru