No.011 D

見つかりにくい点は, ある2本の道から等距離であるか, ある2つの住居から等距離であるか, グレイの制約の端かである.

よってすべての2本の道の角の二等分線, すべての2つの住居の垂直二等分線, 外周をそれぞれ出し, これらの直線の交点について見つかりにくさをすべて計算する.

角の二等分線の計算は, 二直線を $a_1x+b_1y+c_1=0$, $a_2x+b_2y+c_2=0$ とすると, この二直線から等しい距離にある点は点と直線の距離の公式より,

$$\frac{a_1x+b_1y+c}{ \sqrt{a_1^2+b_1^2} } = \pm \frac{a_2x+b_2y+c}{ \sqrt{a_2^2+b_2^2} }$$

となり, $d_1 = \sqrt{a_1^2+b_1^2}$, $d_2 = \sqrt{a_2^2+b_2^2}$ とすると

$$(a_1d_2 \pm a_2d_1)x + (b_1d_2 \pm b_2d_1)y + (c_1d_2 \pm c_2d_1) = 0$$

となる. ただし, $x, y$ の係数がともに $0$ の場合は解を持たない.

垂直二等分線の計算は, 二点を $(p_1, q_1)$, $(p_2, q_2)$ とすると, この二点から等しい距離にある点は,

$$(x - p_1)^2 + (y - q_1)^2 = (x - p_2)^2 + (y - q_2)^2$$

となり,

$$2(p_2-p_1)x+2(q_2-q_1)+(p_1^2-p_2^2+q_1^2-q_2^2)=0$$

となる.