VPL1_AC - Late Summer Searching

no tags 

Summer is late! Summer is late! For a very important date! The VPL programming contest is about to start and Summer is nowhere to be found. Without Summer, you cannot have a contest based on seasons, so you have to find her quickly!

A system of antennas is placed on the top of the tallest buildings. You can use them to try to detect Summer's position, so you can finally go and get her. However, the antennas are very sensitive to noise, so unless every antenna is visible from every other antenna, the system will not work. Every antenna has an interference radius R, that will block the visibility between two other antennas if their signal passes through it.

Even if the system works, using it is very energy-consuming and quite expensive. Given the positions of the antennas, the cost of using the system is equal to the minimal possible area that encloses every antenna (along with their lines of sight with every other antenna). For simplicity, you can suppose that the physical radius of each antenna is negligible.

You are located in the VPL headquarters building (which has its own antenna), where every other building with an antenna has a position relative to yours. Knowing these positions, and the interference radius for the antennas, your job is to decide whether the system can work or not. And if it can, what will be the cost (in terms of the minimal area covered).

Input

The first line of the input will contain a single integer T, which is the number of test cases that follow. Each test case will begin with a line containing two integers N (the number of antennas) and R (Radius of interference of the antennas). N-1 lines follow, each one containing two integers Xi and Yi, being the relative position of the i-th building with respect to VPL headquarters (which is assumed to be placed at position (0, 0)).

Output

The output of your program should consist of T lines, one for each test case. For each of these test cases you should output a single number, representing the minimum area covered by the system, (Rounded to two decimal places). If the system cannot be used, you should output only the text "NO CONTEST" (quotes for clarity).

Sample

Input
2
4 1
2 0
2 2
0 2
5 1
2 0
2 2
0 2
1 1

Output
4.00
NO CONTEST

Constraints

General Constraints

1 ≤ T ≤ 100

1 ≤ R ≤ 10

-500 ≤ Xi, Yi ≤ 500

Constraints - Subtask 1 (20%)

N = 3

Constraints - Subtask 1 (80%)

3 ≤ N ≤ 100


hide comments
wickedGOD: 2013-05-16 07:51:07

how can we calculate the area of an irregular geometry, please explain

Jayesh Lata: 2013-04-13 22:14:19

Can you explain the area part? How do we define it there?


Added by:Venezuelan Programming League
Date:2013-03-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64