IBM Fencing

The Indigenous Barrier Makers (IBM) are out in the jungle of the Amazon to make fences for the people living there. Many new inhabi- tants 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 de- stroys a lot of trees. Therefore fences are built in layers for the inhabitants for better protec- tion, 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. Fig- ure 1 shows the top view of such a fence lay- out. 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 lay- out, 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. 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.

2/2 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 6 119 119 102 119 94 101 102 83 119 83 127 101 8 83 106 62 111 45 99 42 78 54 59 75 55 92 66 96 87 6 70 97 56 97 49 85 56 73 70 73 77 85 8 143 222 110 244 61 238 35 209 39 169 72 147 121 153 147 181 4 115 226 58 226 51 167 132 167 4 113 212 65 212 65 172 113 172 5 99 205 83 206 71 187 91 179 105 189 2 4 0 0 100 0 100 100 0 100 4 1000 1000 1100 1000 1100 1100 1000 1100 0 Sample Output Case 1: Total Number of Communities 2 Total Cost: Steel Fence: 0.09047417 Million Yuan Wooden Fence: 0.03190241 Million Yuan Case 2: Total Number of Communities 2 Total Cost: Steel Fence: 0.08000000 Million Yuan Wooden Fence: 0.00000000 Million Yuan