Largest Disk
Time Limit: 6 Seconds Memory Limit: 262144 KB
In a l×w rectangle, there are k points with integer coordinates. Your job is to find the largest disk such that it can be enter to the rectangle from the east side (the side with length l) and then it can be moved toward the west side (in order to exit the rectangle from the west side) while avoiding given points inside the rectangle on its path.
Input
The first line of the input includes the number of test cases, 1≤t≤100. Each test case starts with a line containing three integers, 1≤l≤109, 1≤w≤109, and 1≤k≤5000, the number of points. Each of the following k lines contains two integers 0<x<w and 0<y<l, the coordinates of points.
Output
For each test case, print one line containing the answer to the question with exactly 2 digits after decimal point.
Sample Input
3 5 10 0 5 10 2 1 4 4 4 5 10 2 1 7 4 8
Sample Output
2.50 1.50 1.58Submit
Source: 12th Iran Nationwide Internet Contest I