2

1. グレイが考えている見つかりにくさとは、兵器工場から一番近い道路からの距離と、一番近い住居からの距離に依存する。
2. とそれぞれ定義したとき、見つかりにくさを示す評価関数 $f(x, y)$ は、 $f(x, y) = dist_{road}(x, y) + dist_{point}(x, y)^2$ と表すことができる。

• 兵器工場の座標を $(x, y)$
  • 兵器工場から一番近い道路への距離を $dist_{road}(x, y)$
  • 兵器工場から一番近い住居を $dist_{point}(x, y)$

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$ が半角スペース区切りで与えられる。
2. $2$ 行目から $N+1$ 行目までの $N$ 行は道路に関する $3$ つの整数 $a_i$ $b_i$ $c_i$ が半角スペース区切りで与えられる。
3. $N+1$ 行目から $N+1+M$ 行目までの $M$ 行は住居に関する $2$ つの整数 $p_j$ $q_j$ が半角スペース区切りで与えられる。
4. 直線は同一のものが複数与えられる可能性があり、これは座標についても同じである。

見つかりにくさ

f(x, y)

-R≦x,y≦R

1

10^{−6}

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

3.414213562373

図：出力例１を図示したもの

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

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

23.575923118987

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