Problem K: A Polygon And Circles

Problem

$N$個の頂点からなる凸多角形と$M$個の円の中心座標が与えられる。すべての円の半径は$r$である。

以下の条件を満たす最小の実数$r$を求めたい。

条件: 凸多角形の内部のどの点も、少なくとも一つ以上の円に内包されている。

Input

入力は以下の形式ですべて整数で与えられる。

$N$
$px_1$　$py_1$
$px_2$　$py_2$
:
$px_N$　$py_N$
$M$
$cx_1$　$cy_1$
$cx_2$　$cy_2$
:
$cx_M$　$cy_M$

$1$行目には凸多角形の頂点数を表す整数$N$が与えられる。
$2$行目から$2+N-1$行目には凸多角形の各頂点の情報が反時計周りの順で与えられる。$1+i$行目には$i$番目の頂点の座標を表す$px_i$ $py_i$が空白区切りで与えられる。
$2+N$行目には円の数を表す整数$M$が与えられる。
$2+N+1$行目から$2+N+M$行には円の中心座標の情報が与えられる。$2+N+i$行目には$i$番目の円の中心座標を表す$cx_i$ $cy_i$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $3 \le N \le 100$
• $1 \le M \le 100$
• $-10^5 \le px_i, py_i \le 10^5$
• $-10^5 \le cx_i, cy_i \le 10^5$
• 凸多角形の頂点のうちどの3点を選んでも、同一直線上には存在しない

Output

条件を満たす最小の円の半径 $r$ を出力する。
ただし、$10^{-5}$ までの絶対誤差または相対誤差は許容される。

Sample Input 1

4
2 3
1 2
2 1
3 2
4
1 3
1 1
3 3
3 1

Sample Output 1

1.414213562373

Sample Input 2

7
-96469 25422
-55204 -45592
-29140 -72981
98837 -86795
92303 63297
19059 96012
-67980 70342
17
-4265 -14331
33561 72343
52055 98952
-71189 60872
10459 -7512
-11981 57756
-78228 -28044
37397 -69980
-27527 -51966
22661 -16694
13759 -59976
86539 -47703
17098 31709
-62497 -70998
-57608 59799
-1904 -35574
-73860 121

Sample Output 2

75307.220122044484

Note

Link

 

---