IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Занятная задачка, с фантазией...
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

Репутация: -  7  +


Задача следующая:(перевод собственноручный)
Крепость.
Решили казаки крепость соорудить, дабы от иноземных захватчиков проще было отбиваться. Архитекторов среди них не оказалось, поэтому строили как могли. Сначала возвели смотровые башни, а затем, решили строить стены, которые их соединяют. Для повышения обороноспособности каждая стена должна была состоять из сегментов, которые прокладываються от башни к башне, так, чтобы все другие башни оказывались спрятаны за этой сомкнутой стеной(получился выпуклый многоугольник). Между багнями что оказывались внутри, строят другую стену,также как и внешнюю, и так далее, до тех пор пока за каждой стеной остаються башни. Из остатков башен внутри последней стены обязательно сооружают центральное укрепление.
Задание.
В то время у казаков уже был компьютер на деревяных схемах lol.gif mega_chok.gif . Вот нам и предлагаеться написать для него программу , которая подсчитает кол-во замкнутых стен крепости. Учтите что любая стена , кроме внешней, должна полностью лежать внутри другой стены, не касаясь её граней. Грани центрально укрепления не учитываються.
Входящий файл содержит N строчек, каждая из которых содержит пару целыхчисел Х и У- декартовые координаты каждой башни.
Исходящий файл должен содержат единственное целое число кол-во замкнутых стен, или 0 если их невозможно соорудить вообще.

Я лично, вижу только один способ решения, хотя он мне и не нравиться:
с помощью векторов нужно определять положение каждой башни отностительно прямой, которая соединяет две другие произвольные башни,(тоесть нужно чтобы все башни лежали в одно полуплоскости от прямой-стеной), если по внятней, то я имею в виду тот способ, через произведение векторов, которым еще "изящно" определяют лежит ли точка з задаными координатами внутри треугольника з задаными вершинами, или нет (не по площадям получившихся треугольников, а векторами). Сейчас я немного не в состоянии его более точно описать (мозг кипит, башка не думает, и видел я его в 9 класе посл. раз), я завтра этим займусь, но суть по задаче такова: перебираем каждую пару башен, и находим такие которые определяют прямую, относительно которой все остальные башни лежат в одной полуплоскости, когда все такие найдуться, то их удаляем , увеличиваем счотчик стен, и повторяем процес.

Но мне этот метод почемуто не нравиться, я думаю должен быть другой способ решения этой задачи...

Сообщение отредактировано: RathaR -


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

Пусть в массиве p[1..n] хранятся все точки.
1 Упорядочеваем все точки слева направо (по координате X). Первая и последняя точки точно принадлежат выпуклой оболочке.
Оболочку можно поделить на 2 ломанные: они идут от точки p[1] к точке p[n] сверху и снизу. Сперва найдем верхнюю. Начальной точкой оболочки будет точка k = 1.
2 Перебираем точки p[i], где k < i <= n. Следующей точкой оболочки будет такая, что угол между вектором p[k]-p[i] и осью Y минимален.
3 Как только k = n, заканчиваем цикл.
Прикрепленное изображение
4 Нижняя часть оболочки ищется аналогично.

Добавлено через 2 мин.
А вообще, достаточно было просто погуглить =). Например вот: http://algolist.manual.ru/maths/geom/convhull/


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата
А вообще, достаточно было просто погуглить
Гуглить надо было чуть дальше. Эта задача была на олимпиаде 2006 года ФЭТ МГУ. Там есть и изначальное (а не переведенное) условие, и алгоритм решения. Ссылку не дам, ибо автор вопроса должен хоть что-то сделать самостоятельно smile.gif
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 5.12.2020 0:47
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name