Shohurephone, the popular telecom company in Swapnodesh has received a lot of backlash over the last few years for not providing any coverage in the remote areas of the country. Adding insult to injury, the CEO himself got agitated yesterday when the CEO of their rival company, Kobi Ltd, called him from the remote areas of Monkeytown with a Kobi sim and said “Whazzup?” among many things. Thus, Shohurephone is now trying to enlarge their network coverage so that it covers the whole country.
Shohurephone has cell towers spread throughout the country. Installing a new tower is very costly and so, they won’t install any new ones. Instead, they will upgrade their antennas placed in the towers. The network setup in a tower usually covers a circular area of an uniform radius centered at the tower. Let’s define “Network Reach” of a tower to be this radius.
Shohurephone wants to upgrade the network reach of every tower, so that, together they cover all of the country. Additionally, they want their towers to have equal network reach as well for consistency. Upgrading the network reach by any margin is quite costly and they would like to minimize the cost. Calculate the minimum network reach needed for the towers so that together they provide network coverage to each part in the country.
We can describe Swapnodesh to be a convex polygon of points on a Cartesian grid. The vertex is at point . The towers are located within this region, tower being at point .
The first line of the input is an integer which denotes the number of test cases.
For each test case, the first line contains an integer , denoting the number of vertices of the polygon . lines follow, line containing two integers denoting the vertex. The vertices are given in a counter-clockwise order.
Another line follows, containing an integer, , the number of towers. lines follow, line containing two integers .
In all of the input files:
and over all test cases .
For each test case, output the minimum network reach needed for the towers on a single line.
Your output will be considered correct if the absolute or relative difference from the correct result is less than or equal to .
1 4 0 0 6 0 6 6 0 6 2 1 1 5 5
ABCD (in red) is the polygonal shape of the country and E, F are the two towers. They have network coverage all over the green areas, thus covering the country.