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. The video game is highly realistic, so the damage you do to the monster is ex- actly the integral of the intersection area of your projectile and the monster, over time. Formally, the damage D is com- puted as follows: ∫ 0 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 Fig 2. The change of intersection area 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. D = area(t)dt ∞
2/2 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. 12162.0.1 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 3 4 1 -1 3 -1 31 11 4 -1 -1 -1 1 -3 1 -3 -1 4 1 -1 3 -1 31 11 3 -1 0 -3 1 -3 -1 3 30 11 1 -1 3 -1 0 -3 1 -3 -1 Sample Output Case 1: 8.000000 Case 2: 4.000000 Case 3: 2.666667