提示: 欢迎访问OurACM平台。
Problem 1918 John’s Direction

Accept: 49    Submit: 215
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

John has encountered a problem recently. He will draw n polygons Pi (1≤i≤n) in the plane and a point Q. The point Q can move in all directions. If point Q can be translated an arbitrary distance in direction d without colliding with Pi, we call direction d as safe direction. Now we should determine the total degrees of safe direction.

The polygon is drawn as follows. He starts from the origin, the initial direction is north. There are three types of operations he can make: “F x”: move forward x units of length. ‘L’: turn left 90 degrees. ‘R’: turn right 90 degrees. At the end, he will return to the origin. He never visits the same point twice except for the origin, so it encloses a polygon. Figure 1 and Figure 2 are all valid. Figure 3 shows the degrees of safe direction.

Given n polygons and a point Q, your task is to find the total degrees of safe direction.

Input

The first line of the input contains an integer T (T <= 20), indicating the number of cases. Each case begins with a line containing three integers n, x and y(1 <= n <= 10), the number of polygons and the coordinates of the point Q(x,y). You should note that the number of vertices (the points generated by “F x” operation) in each polygon are at least 4 and at most 80,000, the area of each polygon is not zero. For each polygon begins with a line containing three integers L, u, v (1 <= L <= 160,000), the number of operations and the coordinates of the origin point (u,v). The following L lines describe the operations as said above. All coordinates of the points are between -1,000,000 and 1,000,000, inclusive. If point Q is on the boundary of those polygons, you should also calculate the result.

Output

For each test case, print a line containing the test case number (beginning with 1) and the total degrees of safe direction. Print your result rounded to 2 decimal places (as the format in sample).

Sample Input

3 1 -4 1 15 0 0 F 2 L F 4 R F 1 R F 5 R F 5 R F 3 R F 2 R F 2 2 -1 0 7 0 0 F 1 R F 1 R F 1 R F 1 8 0 -1 R F 1 R F 1 R F 1 R F 1 1 0 0 7 0 0 F 1 R F 1 R F 1 R F 1

Sample Output

Case 1: 213.69 Case 2: 278.13 Case 3: 270.00

Source

2010年全国大学生程序设计邀请赛(福州)

Submit  Back  Status  Discuss