Server Time: Fri Sep 25, 2020 12:00 am
 Welcome ( logout )
F - Aladdin and the Rocky Mountains
 PDF (English) Ranklist
 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 (ax, 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

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 ax, n denotes the number of picks in the mountain, and ax denotes the x co-ordinate of Aladdin. Each of the next n lines contains two integers: xi and yi forming the mountain. Assume that x1 > ax, y1 = 0 and xi > xi-1 for 2 ≤ i ≤ n. Values for the co-ordinates will lie in the range [0, 50000].

# Output

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.

# Output for Sample Input

1

6 2

4 0

6 2

7 3

8 2

9 2

10 5

Case 1: 4.5061638255

# Note

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan