D - きつねさんからの挑戦状 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

2013.01.19 21:56 R の範囲を変更しました。

問題文

きつねのグレイは街中に秘密の兵器工場を作ろうとしています。
彼は人間たちに工場の場所を知られたくないので、人間の住居が少ない辺鄙な場所に工場を建てようとしています。
あなたはグレイの工作活動を阻止するために派遣された某国のエージェントで、任務のために某国から街の地図が支給されています。
街は道路と住居で構成されており、それらは全て地図に記されています。
地図は 2 次元平面で、道路は直線、住居は座標であるとみなします。

いま別のエージェントからグレイが工場を建てる場所についての情報が入りました。
  1. グレイが考えている見つかりにくさとは、兵器工場から一番近い道路からの距離と、一番近い住居からの距離に依存する。
    • 兵器工場の座標を (x, y)
    • 兵器工場から一番近い道路への距離を dist_{road}(x, y)
    • 兵器工場から一番近い住居を dist_{point}(x, y)
    とそれぞれ定義したとき、見つかりにくさを示す評価関数 f(x, y) は、 f(x, y) = dist_{road}(x, y) + dist_{point}(x, y)^2 と表すことができる。
  3. グレイは評価関数 f(x, y) が最も大きくなるような座標 (x, y) に兵器工場を建てる。
  4. 兵器工場の座標 (x, y)　は、ある整数 R に対して -R≦x,y≦R を満たす。
  5. 座標 (x, y)　はともに実数である。

あなたはこの情報と地図を頼りに、グレイが兵器工場を建設する予定の場所を突き止めるため、評価関数 f(x, y) の最大値を求めることにした。

入力

入力は以下の形式で標準入力から与えられる。 
N M R
a_{0} b_{0} c_{0}
:
a_{N-1} b_{N-1} c_{N-1}
p_0 q_0
:
p_{M-1} q_{M-1}
  1. 1 行目には 3 つの整数 N M R が半角スペース区切りで与えられる。
    • N は道路の個数であり、 1≦N≦16 を満たす。
    • M は住居の個数であり、 1≦M≦16 を満たす。
    • R はグレイが建設する兵器工場の座標 (x, y) に関する制約で、 1≦R≦1,000 を満たす。
  2. 2 行目から N+1 行目までの N 行は道路に関する 3 つの整数 a_i b_i c_i が半角スペース区切りで与えられる。
    • i番目の道路は直線 a_ix + b_iy + c_i = 0 として与えられる。
    • a_i は -1,000≦a_i≦1,000 を満たす。
    • b_i は -1,000≦b_i≦1,000 を満たす。
    • c_i は -1,000≦c_i≦1,000 を満たす。
    • a_i = 0 かつ b_i = 0 となるようなケースは与えられない。
  3. N+1 行目から N+1+M 行目までの M 行は住居に関する 2 つの整数 p_j q_j が半角スペース区切りで与えられる。
    • j番目の住居は座標 (p_j, q_j) として与えられる。
    • p_j は -1,000≦p_j≦1,000 を満たす。
    • q_j は -1,000≦q_j≦1,000 を満たす。
  4. 直線は同一のものが複数与えられる可能性があり、これは座標についても同じである。

出力

見つかりにくさを示す評価関数 f(x, y) の -R≦x,y≦R における最大値を 1 行で出力せよ。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
また、出力の最後には改行をいれること。

入力例 1

4 4 1
1 1 2
1 1 -2
1 -1 2
1 -1 -2
1 1
1 -1
-1 1
-1 -1

出力例 1

3.414213562373
図：出力例１を図示したもの
  • 座標 (0, 0) に兵器工場を建設すると、評価関数の値が最大となり、その値は 3.414213562373 になります。

入力例 2

7 5 3
-2 2 1
5 5 3
5 4 1
-2 2 -1
0 3 -4
-3 -1 -1
2 0 2
-2 4
-3 -3
4 3
4 -5
2 5

出力例 2

23.575923118987
  • 座標 (1.35714285714286, -1) に兵器工場を建設すると、評価関数の値が最大となり、その値は 23.575923118987 になります。