Signal Coverage

Question

Problem Description
GSM, Global System for Mobile Communications, is the world's most popular standard for mobile telephone systems. CMCC, China Mobile Communications Corporation, has almost 500,000 GSM base stations, but some cellphone users still complain about the signal coverage problem. Because of building block or some other reasons, we can assume that a base station covers an area of a simple polygon, and they don’t intersect with each other. We have a map that contains some simple polygons which represents the coverage of base stations. For the coverage ratio statistics, we drew a segment on the map, and we consider the C/L be the coverage ratio. C is the length of segment to be covered; L is the length of the segment we drew.
Please notice that, if a part of the segment can be considered as covered, that part must be inside or on the boundary of the polygon.

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two coordinate, indicating the start and the end of the segment we drew. Then followed an integer, N, indicating there are N simple polygons. Each polygon starts with an integer, C, and C coordinates followed.

Technical Specification

1. 1 <= T <= 20
2. The number of all the points on the map is less than 100,000.
3. The coordinate of all the points consists of integers, and the value is in the range of [-100000, 100000]

Output
For each test case, output the case number first, then a coverage ratio with two decimal digits.

Sample Input
2

0 0 2 0
1
4 0 0 1 0 1 1 0 1

0 0 2 0
1
4 0 -1 1 -1 1 1 0 1

Sample Output
Case 1: 50.00%
Case 2: 50.00%

Answer 1

http://www.scholarpedia.org/article/Global_system_for_mobile_communications_(GSM)