acm
cz
acm
cz
Dept. of Computer Science and Engineering, Czech Technical University in Prague
Faculty of Mathematics and Physics, Charles University in Prague
Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava
Faculty of Informatics and Information Technologies, Slovak University of Technology
Faculty of Informatics, Masaryk University
Faculty of Management Science and Informatics, University of Zilina
CTU Open Contest 2008
Wooden Fence
fence.c, fence.C, fence.java, fence.p
Did you ever wonder what happens to your money when you deposit them to a bank account.
All banks hold such deposits in various assets, such as gold, stocks, obligations, deposits in other
banks, loans, bonds, and many others. Due to the financial crisis and instability of the stock
exchanges, many banks find out that stocks are not very reliable and their possession may be
too risky.
Therefore, the banks now prefer other assets, especially gold. The main trouble with gold is
that there is only a limited amount of it in the whole world. And it is not enough to cover all
money held by all banks. (Wait, isnít this the real reason of the crisis.)
If there is not enough gold, other commodities must be exploited instead. The International
Bank of Monetania (IBM) has recently come up with an idea of using very old and valuable
trees as their assets. They bought a piece of land with several such trees and now expect their
value to grow. Literally, of course.
Unfortunately, the trees are threatened by wildlife, because animals do not understand their
value and nibble them. Moreover, there is a permanent danger of theft. As a result, it is
absolutely necessary to build a good solid fence around the trees.
The IBM quickly realized that the only suitable material available to build the fence is the wood
from the trees themselves. In other words, it is necessary to cut down some trees in order to
build a fence around the remaining ones. Of course, to keep the maximum value, we want to
minimize the value of the trees that had to be cut. You are to write a program that solves this
problem.
Input Specification
The input contains several test cases, each of which describes one piece of land. Each test case
begins with a line containing a single integer N,2. N . 16, the total number of trees. Each
of the subsequent N lines contains 4 integers X
i
, Y
i
, V
i
, L
i
separated by at least one space.
The four numbers describe a single tree. (X
i
,Y
i
) is the position of the tree in the plane, V
i
is
its value, and L
i
is the length of fence that can be built using the wood of the tree. You may
assume that 0 . V
i
,L
i
. 10 000 and -10 000 . X
i
,Y
i
. 10 000. No two trees in a test case will
grow at the same position.
The input ends with a line containing zero in place of N.
pg_0002
Output Specification
For each test case, compute a subset of the trees such that, using the wood from that subset, the
remaining trees can be enclosed in a single continuous fence. Find the subset with the minimal
total value. For simplicity, regard the trees as having zero diameter.
Output one line with the sentence ďThe lost value is T .", where T is the minimal value of
the trees that must be cut.
Sample Input
6
0083
1432
2171
4123
3546
2398
3
30103
5-32025
7-33032
2
100054
0 100 4 5
5
0 0 10 10
0 1 10 10
1 0 10 10
1 1 10 10
50 50 8 4
0
Output for Sample Input
The lost value is 9.
The lost value is 20.
The lost value is 4.
The lost value is 8.