|
Название задачи: Ограда сада . |
 |
Условие
Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал небольшое собрание редких и весьма ценных деревьев. Для того, чтобы обезопасить свою коллекцию от злоумышленников, король приказал возвести вокруг нее высокий забор. Главный королевский колдун был назначен ответственным за исполнение этого поручения.Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение.
Вы должны написать программу, решающую задачу, с которой столкнулся
главный королевский колдун. Постройте такое подмножество деревьев с
наименьшей суммарной стоимостью, что, срубив деревья из этого
подмножества, можно построить один забор, огораживающий все оставшиеся
деревья. Если существует более одного подмножества с минимальной
стоимостью, выберите то, в котором меньше деревьев.
Входные данные
В первой строке входного файла записано целое число N – количество
деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N
строк содержит четыре целых числа xi, yi, vi, li, описывающих очередное дерево.
(xi, yi) – это координаты дерева на плоскости, vi
– его стоимость, а li
– длина забора, который может быть построен из этого дерева. Все числа vi, li, а также
абсолютные величины xi
и yi
– целые числа из диапазона [0, 10000]. Считается,
что деревья имеют нулевой радиус.
Выходные данные
Первая строка выходного файла должна содержать номера деревьев, которые
необходимо срубить, разделенные пробелом. Во вторую строку выведите
излишек срубленного материала.
Пример входного файла
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8
Пример выходного файла
2 4 5
3.16
Решение
Скачать архив тестов и решенийДля решения этой задачи будем перебирать все возможные подмножества деревьев для рубки. Для каждого анализируемого подмножества M нужно найти выпуклую оболочку оставшихся деревьев и проверить, что ее периметр не превышает длины забора, который мы можем построить из деревьев M. Рассмотрев все такие подмножества M, выберем то, которое имеет минимальную суммарную стоимость деревьев.
Для сокращения перебора не следует рассматривать подмножества с большей стоимостью, чем стоимость наилучшего из ранее найденных. Поэтому важно быстро найти решение, близкое к оптимальному.
