Network Reach

reborn Criterion 2022 Round 19
Limits 1s, 256 MB

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 nn 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 PP of mm points on a Cartesian grid. The ithi^{th} vertex is at point (ai,bi)(a_i, b_i). The nn towers are located within this region, ithi^{th} tower being at point (xi,yi)(x_i, y_i).


The first line of the input is an integer TT which denotes the number of test cases.

For each test case, the first line contains an integer mm, denoting the number of vertices of the polygon PP. mm lines follow, ithi^{th} line containing two integers ai,bia_i, b_i denoting the ithi^{th} vertex. The vertices are given in a counter-clockwise order.

Another line follows, containing an integer, nn, the number of towers. nn lines follow, ithi^{th} line containing two integers xi,yix_i, y_i.

In all of the input files:

  • 1T1031 \le T \le 10^3.

  • 3m1033 \le m \le 10^3.

  • 1n1031 \le n \le 10^3.

  • 109ai,bi,xi,yi109-10^9 \le a_i, b_i, x_i, y_i \le 10^9.

  • n\sum n and m\sum m over all test cases 103\le 10^3.


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 10610^{-6}.


0 0
6 0
6 6
0 6
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.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.