In a water refining plant, the flow of im- pure water is passed through a network consisting of straight-line water pipes. There are several pipes in the network. Each of them performs a particular oper- ation in the refinement process. So, the impure water must pass through each of them. These pipes are placed on a 2D grid like surface and the two endpoints of each pipe can be described by a pair of integer coordinates. Every two pipes sharing an endpoint are joined at that lo- cation through a multi-way connector. Each connector has one or two pairs of openings. All the openings are connected to some pipe. In addition to the openings for joining pipes, each connector can be connected to a water tank. So, in a single refinement process, the tank full of impure water is connected to one of the connectors, all of the water is passed through the pipe networks as necessary and then purified water is brought back to the tank. It might be important to clarify that there is only one tank in the system and there is no additional pipe to send fresh water back to the tank once the purification is done. Also, in order to prevent overuse of the pipes, in a single refinement process water is allowed to pass through any pipe exactly once. This single flow through a pipe can be in any direction. Now, waters can move freely through the pipes but if they need to change direction in the connectors, external energy must be supplied by using pumps. The amount of rotation can be expressed as a function of the pump’s energy. For a network, TRA (Total Rotation Amount) can be calculated in the following way. After the flow is complete, a polygon is created by tracing the path of water flow inside the network. Then at each node of the polygon, we take the smallest angle between the two lines adjacent to it. By summing up these angle values for all the nodes, we get the TRA. A pump with e units of energy can provide Ae3 + Be2 + Ce + D full circle amount of TRA where A, B, C, D are non-negative integer constants. You are given the description of a network and the A, B, C, D, e values of a pump. Your task is to determine the maximum percentage of energy that can remain unused after completing a single refinement process. Percentage can be found by the formula — (unused energy/total energy) ∗ 100. Input There will be at most 40 cases in the input file. Each test case starts with a line with 6 integers, E (3 ≤ E ≤ 20000), A, B, C, D (0 ≤ A,B,C,D ≤ 5) and e(0 ≤ e ≤ 50). E is the number of pipes in the network while A, B, C, D and e are the description of the pump as mentioned in the statement above. Each of the following E lines contains 4 integers: x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 10, 000), denoting the coordinates of two endpoints of a pipe. The final test case is followed by a line containing a single ‘0’ denoting end of input. Output For each test case, print the case number at first. Then if it is possible to complete a flow in this network using the given pump, print the maximum possible percentage of unused energy rounded to 2
2/2 digits after decimal point. If it’s not possible to complete a flow cycle, report so. Check sample input for exact formatting. Sample Input 411111 1221 2110 1001 0112 411100 1221 2110 1001 0112 0 Sample Output Case 1: 75.00 Case 2: Impossible