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