Занятная задачка, с фантазией... Опции

[RathaR]

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

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

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

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

[Archon]

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

Пусть в массиве 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/

[volvo]

А вообще, достаточно было просто погуглить

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