Time Limit: 3 second(s) | Memory Limit: 32 MB |
It's said that Aladdin had to solve seven mysteries before getting the Magical Lamp which summons a powerful Genie. Here we are concerned about the sixth mystery.
After the Happy Garden, Aladdin reached a place where he found a huge area of Rocky Mountains. He could barely see other than the rocks. His target was to reach the highest pick, such that all parts could be observed by him. He was searching for the layer of 3-Eyed Monsters where the lamp was located. So, he started climbing and finally managed to find the layer.
However, here we are concerned about a similar problem. Assume that the mountains are described by 2D co-ordinates and have negligible thickness. Aladdin is standing in a position which is (a_{x}, 0); your target is to find the area that can be seen by him from this position. Aladdin cannot see a point if there is any point between him and the object point. For example, in the picture, Aladdin's co-ordinate is (2, 0) and the points (4, 0), (6, 2) (7, 3), (8, 2), (9, 2) and (10, 5) form the mountain. Y co-ordinate 0 means it's ground. He can see the green sides (as in picture). You have to find this area.
Input starts with an integer T (≤ 30), denoting the number of test cases.
Each case starts with a blank line. Next line contains two integers n (2 ≤ n ≤ 20000) and a_{x}, n denotes the number of picks in the mountain, and a_{x} denotes the x co-ordinate of Aladdin. Each of the next n lines contains two integers: x_{i} and y_{i} forming the mountain. Assume that x_{1} > a_{x}, y_{1} = 0 and x_{i} > x_{i-1} for 2 ≤ i ≤ n. Values for the co-ordinates will lie in the range [0, 50000].
For each case, print the case number and the total area of the Mountain sides (above ground) that can be observed by Aladdin. Errors less than 10^{-3} will be ignored.
Sample Input |
Output for Sample Input |
1
6 2 4 0 6 2 7 3 8 2 9 2 10 5 |
Case 1: 4.5061638255 |
Dataset is huge, use faster I/O methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |