Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Wall

Limits 1s, 512 MB

A long time ago in a galaxy far, far away, there lived two groups of people named Stormtroopers and Rebels who were always fighting with each other. They lived in a planet Tatooine which was a flat 2 dimensional land. There were N Stormtroopers and M Rebels in Tatooine. You are given N pair of integers denoting the coordinate of Stormtroopers and M pair of integers denoting the coordinate of Rebels. They don’t like each other.

So they want to build a wall between them. You can assume that it is always possible to build a wall between them. A wall is a line in the two dimensional plane. So you can always find such a line which can divide the plane into two separate part such that all the Stormtroopers are in one side of the wall and all the Rebels are on the other side of the wall. You have to find the wall that maximizes the minimum distance from any Stormtrooper or Rebel to the wall.

Input

First line of the input gives the number of test cases, T (1 ≤ T ≤ 35) to follow.

For each test case, first line gives one integer, N (1 ≤ N + M ≤ 200000).

The next N lines has a pair of integers X1i , Y1i (-107 ≤ X1i, Y1i ≤ 107) each denoting the coordinate of the Stormtroopers.

Next line gives one integer, M (1 ≤ N + M ≤ 200000).

Next M lines has a pair of integers X2i , Y2i (-107 ≤ X2i, Y2i ≤ 107) each denoting the coordinate of the Rebels.

Output

Output the maximum of the minimum distances from any of the points to the dividing wall (acceptable error is 1e-6).

Sample

InputOutput
2
1
0 1
1
0 2
2
0 0
1 0
2
0 1
1 1
0.5
0.5



Discussion
Statistics

11% Solution Ratio

AashiqEarliest, 11M ago

AashiqFastest, 0.5s

AashiqLightest, 6.3 MB

AashiqShortest, 8476B

Submit

Login to submit