Лабораторный практикум по информатике
Задача 2. «Здесь будет город-сад»
жүктеу/скачать 1,1 Mb.
|
| Задача 2. «Здесь будет город-сад». Жители одного дома города Х решили высадить у себя во дворе несколько деревьев. Так как жильцы не смогли договориться, как должны быть расположены посадки, то каждый посадил дерево в том месте двора, где ему захотелось. После проведения посадок полученный сад решили обнести забором. Но пока доски не привезли, деревья обвязали одной длинной веревкой.
Исходная информация: N – количество деревьев в саду, (xi, yi) – ко- ординаты деревьев, i = 1, 2, …, N. Так как были высажены молодые са- женцы, то их толщиной можно пренебречь. Требуется определить, к каким из посаженных деревьев надо при- вязать веревку так, чтобы все деревья оказались внутри обнесенной зо- ны, а длина веревки была минимальная. Эта и подобные ей задачи сводятся к определению для заданного множества точек на плоскости выпуклой оболочки, то есть выпуклого многоугольника с вершинами в некоторых точках из заданного множе- ства, охватывающего все его точки. В [2] приведено несколько вариан- тов решения такой задачи с учетом временных затрат на выполнение алгоритмов. Здесь мы рассмотрим способ, использующий свойства ска- лярного произведения векторов. Будем строить выпуклую оболочку в порядке обхода участка по ча- совой стрелке. Найдем самую левую точку М0 = (x0, y0), x0 = min{xi}. Если таких точек несколько, то возьмем самую нижнюю из них. Эта точка на- верняка принадлежит искомой выпуклой оболочке. Зададим первона- чальный вектор a0 с началом в точке (x0, y0), параллельный оси Oy. Следующей точкой оболочки будет такая точка М1, чтобы вектор a1 с началом в точке М0 и концом в точке М1 образовывал с первоначаль- ным вектором a0 минимальный угол. Если таких точек несколько, то выбирается точка, расстояние до которой максимально. Далее процесс продолжаем, то есть ищем точку М2 с минимальным углом между вектором a1 и вектором a2 с началом в точке М1 и концом в точке М2, затем точку М3 и т. д. Процесс прекращаем, когда дойдем до первой выбранной точки или количество точек в оболочке станет равно N. Для определения угла между векторами используется скалярное произведение. Причем сам угол можно не вычислять, так как мини- мальному углу соответствует максимальный косинус угла. жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|