Todaiji

Time Limit : 2 sec, Memory Limit : 131072 KB

F : Todaiji / 東大寺

Problem

づいあ君は旅行が大好きである。奈良旅行に訪れたづいあ君は、東大寺にある柱の穴をくぐることにした。しかし、づいあ君は最近太りだしたため、穴に引っかかってしまうかもしれない。そこでづいあ君は、どこまで太っても大丈夫かを調べるプログラムを書くことにした。

簡単のため問題は平面上で考える。穴は2本の折れ線で、づいあ君は円で表すこととする。折れ線 1 は点 (0,0) が始点、点 (1000,0) が終点である。折れ線 2 は点 (0,1000) が始点、点 (1000,1000) が終点である。 づいあ君の全身が x < 0 の領域にある状態から、2 本の折れ線の間を通り、 x > 1000 の領域にづいあ君の全身が出た状態に到達できるような最大の直径を求めてほしい。通過する際の経路は自由であり、円が折れ線に接しても良い。

Input

入力は次のような形式で与えられる。

N1
x11 y11
x12 y12
...
x1N1 y1N1
N2
x21 y21
x22 y22
...
x2N2 y2N2

  • N1 は1つ目の折れ線を構成する点の数である。
  • x1i, y1i は、1つ目の折れ線を構成する i 番目の点の座標である。(x1i, y1i) と (x1(i+1), y1(i+1)) が結ばれる。
  • (0,0) と (x11 , y11)、(x1N1 , y1N1) と (1000,0) がそれぞれ線で結ばれる。
  • 2つ目の折れ線についても折れ線1と同様の形式で入力される。ただし、(x21 , y21) と結ばれるのは (0,1000)、(x2N2 , y2N2) と結ばれるのは (1000,1000) である。

Constraints

  • 入力は全て整数である。
  • 1 ≦ N1, N2 ≦ 50
  • 0 ≦ xij , yij ≦ 1000
  • xijxi(j+1)
  • 折れ線は自分自身と交わらない。
  • 2 本の折れ線は交わらない。

Output

2 本の折れ線の間を通過できる、づいあ君の体の最大の直径を1行で出力せよ。10-6 までの誤差は許される。

Samples

Sapmle Input 1

2
300 300
700 300
2
300 700
700 700

Sapmle Output 1

400.0000000000

Sapmle Input 2

31
53 334
96 201
99 129
114 365
123 39
186 257
195 247
233 335
256 79
302 217
404 302
411 222
428 422
433 388
441 443
468 309
497 408
518 218
537 361
538 193
541 447
580 16
606 185
610 178
737 421
754 210
805 418
849 416
876 262
878 220
948 207
28
7 919
89 640
145 656
152 963
204 558
252 630
269 690
325 629
357 583
454 593
523 648
538 949
541 821
559 655
581 614
593 877
607 571
631 817
682 942
776 529
810 606
813 598
834 778
838 999
910 661
920 824
982 517
987 689

Sapmle Output 2

114.7257599670

サンプル 2 を図示するとこのようになる。


Source: Aizu Competitive Programming Camp 2014 Day3 , Japan, 2014-09-25