|
H |
IBM
Fencing |
|
|
|
|
|
Figure 1: A fence plan. The steel fences are drawn with gray lines and the wooden fences are drawn with brown dashed lines. This figure corresponds to the first sample input and output. |
The Indigenous Barrier Makers (IBM) are out in the jungle of the Amazon to make fences for the people living there. Many new inhabitants are coming to stay there so IBM has to build many fences. But all the fences are not of the same type; there are some wooden fences and some steel fences. And the cost of making the steel fence is much higher than the wooden fence. So IBM wants to build wooden fence whenever it is possible to minimize the total cost. But ACM (Association of Consumer-right Monitoring) is more than concerned about the safety of the people and about saving trees.
With the adverse effect of climate change around the world, wild fire is a common threat now, so wooden fence is sometimes very risky in places like Amazon. Also make wooden fence we need a lot of woods which eventually destroys a lot of trees. Therefore fences are built in layers for the inhabitants for better protection, safety and privacy. To stay safe as well as to save cost, ACM and IBM decides to build the outermost fence with steel and then a wooden fence and steel fence alternately inwards. Figure 1 shows the top view of such a fence layout. The grey lines indicate that steel fence will be built by IBM along those lines. The brown dashed lines indicate that wooden fences will be built along those lines. Given a fence layout, you will have to help ACM and IBM to find out the total cost for building fences by writing a program. Your solution must be quite efficient.
Input
The input file contains at most 12 sets of inputs. The description of each set is given below:
The first line
of each set is an integer N (0<N<501) which denotes how many fences are
to be built. Each of the next N lines describes a fence ring. Each fence ring
is described as a complete convex polygon. The description starts with an
integer M (0<M<1001) which denotes the total number of wall segments that
make up the fence ring. This M is followed by M pairs of floating-point numbers
(x1, y1), (x2, y2), (x3,
y3),
…, (xM,
yM).
These integers denote that the fence is made by connecting the points (x1, y1) with (x2,
y2), (x2, y2) with (x3,
y3), … , (xM-1,
yM-1) with (xM, yM)
and (xM,
yM)
with (x1, y1). You can assume that the
fence layout will be a valid one – (a) two fence rings will not intersect (b)
fence rings will always be described as a convex polygon. You cam also assume that absolute value of all the coordinates
will be less than 400000.
Input is terminated by a line containing a single zero.
Output
For each line of input produce 5 lines of output.
The first line contains the serial of output.
The next line reports the total number of communities. A community is comprised by people who share a common outermost boundary.
The third line contains the string “Total Cost:”
The fourth and fifth line reports the total cost to build the steel fence and wooden fence respectively. The cost has to be reported million Yuan rounded to the eight digits after the decimal. Assume that the cost of building steel fence is 100 Yuan/unit length and that for Wooden fence is 50 Yuan/unit length.
Print a blank line after output for each set of input. Look at the output for sample input for details. Output difference due to small precision error will be ignored.
Sample
Input
|
8 8 112 134 73 141
41 119 32 82 54 50 92 43 124 65 132 103 |
Output
for Sample Input
|
Case 1: Case 2: |
Problem Setter: Shahriar Manzoor, Special Thanks: Derek Kisman