Лабораторный практикум по информатике


Задача 2. «Здесь будет город-сад»



бет71/83
Дата06.01.2022
өлшемі1,1 Mb.
#15674
түріПрактикум
1   ...   67   68   69   70   71   72   73   74   ...   83
Задача 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   ...   67   68   69   70   71   72   73   74   ...   83




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет