Shooting the Monster

Input: Standard Input

Output: Standard Output

In a Video game, you want to shoot a projectile towards a monster. The monster is a polygon in the right half (i.e. positive x) of the screen. He's too big to be able to move. Your projectile will also be a polygon which flies horizontally from the left half of the screen to the right boundary of the screen, at a constant speed v = 1. The projectile will not stop until its leftmost point hits the right boundary of the screen (i.e. it goes through the monster completely). See Fig 1. for an example screen. Note that even though the projectile goes through it, the monster never moves, and it will never change its shape.


Fig 1. In a video game, you shoot a projectile (green) towards a monster (red). The left picture corresponds to the initial situation (t=0), the right picture corresponding to the situation when t=3. The intersection area is in yellow.

Fig 2. The change of intersection area

The video game is highly realistic, so the damage you do to the monster is exactly the integral of the intersection area of your projectile and the monster, over time. Formally, the damage D is computed as follows:

Where area(t) is the intersection area at time t. In the right picture in Fig 1, you can see area(3) = 1, which is the area of the yellow triangle.

For the scenario in Fig 1, we can see how area(t) changes over time in Fig 2 (we can examine area(3) = 1). By the definition of integral, D is exactly the area below the curve, i.e. the blue area in Fig 2.

Your task is to compute the damage, given the information of the projectile and the monster.

Input

The first line contains T(1 ≤ T ≤ 25), the number of test cases. Each test case contains the description of the monster, then the projectile, in the same format.

Each polygon begins with a line containing an integer n (3 ≤ n ≤ 50), the number of vertices. Then n lines followed, the coordinates of the vertices, in counterclockwise order. The middle line of the screen is x = 0, the left and right boundaries are x = -500 and x = 500, respectively.

For the first polygon (monster), all x coordinates satisfy 0 < x < 500, while for the second polygon (projectile), all x coordinates satisfy -500 < x < 0. All y coordinates satisfy -500 < y < 500. All coordinates are integers.

Output

For each test case, print the case number and the damage to the monster, to six decimal places. Look at the output for sample input for details.

Sample Input Output for Sample Input

1 -1

3 -1

3 1

1 1

-1 -1

-1 1

-3 1

-3 -1

1 -1

3 -1

3 1

1 1

-1 0

-3 1

-3 -1

3 0

1 1

1 -1

-1 0

-3 1

-3 -1

Case 1: 8.000000

Case 2: 4.000000

Case 3: 2.666667

Problem setter: Rujia Liu, Special Thanks: Mahmudur Rahman