理想キャニスタ (英語名 Ideally Compact Packaging Canisters, ICPC) 株式会社は,
キャニスタ (円筒型容器) の専門メーカーで,
顧客の注文に応じたキャニスタを設計・製造している.
同社は異なる製品二つを一緒に入れるキャニスタの注文を受けた.
製品の形状は共に凸多角柱で,高さはまったく同じである.
キャニスタの内側は,高さが製品の高さと等しい精密な円柱状にしたい.
製品はキャニスタ内に縦向きに配置されなければならない.
すなわち,どちらの製品の底面も容器の底面に沿って配置しなければならない.
製品はキャニスタ内のどこにどの向きに置いても良いが,
上下逆さまに置いてはならないし,
製品を重ねて置いてもならない.
製品同士や容器の内面が接触するのは構わない.
注文主はキャニスタをなるべく小さくしたいと望んている.
あなたには二つの製品が収まるキャニスタの底面の最小直径を見つけてほしい.
図 H-1 二製品の最小キャニスタへの収納例.
入力は高々 50 個のデータセットからなる.
各データセットは次の形式で表される.
n
xa,1 ya,1
...
xa,n ya,n
m
xb,1 yb,1
...
xb,m yb,m
n (3 ≤ n ≤ 40) は片方の製品の底面の多角形の頂点数である.
続く n 行にはそれぞれ二つの整数,底面多角形の頂点の x-座標と y-座標が与えられる.
それらは −1000 以上 1000 以下である.
頂点は反時計回り順に並んでいる.
底面の多角形は必ず凸である.
その後にまったく同様にもう一方の製品の底面多角形の記述が与えられる.
入力の終わりは,ゼロだけからなる行で表される.