Guard

Time Limit: 15000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 3370
64-bit integer IO format: %I64d      Java class name: Main

Description

You got a new guard offer yesterday. Now you are at the company, and your boss asks you to stand at somewhere to do your job -- guard.
You can treat the building as a simple polygon, and your job is finding a position to make sure that you can see the largest area. Please notice that, you have a range of vision, that you cannot see what is out of that range. The wall of building can also block your sight.

Look at that image; if you stand at the middle then you can see the gray area.

Input

The input consists of multiple test cases. The first line of each case contains two integers n (0 <= n <= 10) and r(0 <= r <= 100). The next n lines contain a simple polygon that consists of n points, indicating the building. The absolute value of each coordinate won’t be more than 100.
The last case is followed by a line containing two zeros which should not be processed.

Output

Output the largest area that you can see. Please take it with two fractional digits and make sure that your program won’t output “-0.00”.

Sample Input

3 1
0 0
2 0
0 2

3 1
0 0
1 0
0 1
0 0

Sample Output

1.81
0.50

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .