ARC042B - アリの高橋くん - 競プロはじめました

考えたこと

もっと簡単な方法があるんだろうな，とは思いつつも，計算で解が出せるので解いてしまった．

現在地$(x_{0}, y_{0})$を中心とする円で各辺に接するものの半径を求め，それらのうちの最小値が答えになる．

隣り合う頂点の座標を$(x_{1}, y_{1})$，$(x_{2}, y_{2})$とする．$x_{1}=x_{2}$なら$|x_{1} - x_{0}|$が辺までの距離になり，$y_{1}=y_{2}$なら$|y_{1} - y_{0}|$が辺までの距離になる．以下では，それ以外の場合を考える．

2点$(x_{1}, y_{1})$，$(x_{2}, y_{2})$を通る直線の方程式は

\begin{aligned}
&y = ax + b \\
&
\begin{cases}
\, a = (y_{2} - y_{1}) / (x_{2} - x_{1}) \\
\, b = - a x_{1} + y_{1}
\end{cases}
\end{aligned}

である．これを直線$l$と呼ぶことにする．

$(x_{0}, y_{0})$を中心とする円が直線$l$と接するとき，その接点を$(x_{t}, y_{t})$とする．2点$(x_{0}, y_{0})$，$(x_{t}, y_{t})$を通る直線は，直線$l$と直交するので

\begin{aligned}
&y = - x/a + c \\
&c = x_{0} / a + y_{0}
\end{aligned}

と表せる．

これを直線$l$の方程式と連立させると，接点$(x_{t}, y_{t})$が

\begin{aligned}
x_{t} &= a(c - b) / (a^{2} + 1) \\
y_{t} &= - (c - b) / (a^{2} + 1) + c
\end{aligned}

と求まる．

よって，点$(x_{0}, y_{0})$から直線$l$までの距離は

\begin{aligned}
\sqrt{(x_{t} - x_{0})^{2} + (y_{t} - y_{0})^{2}}
\end{aligned}

で与えられる．

以上をすべての辺に対して計算し，その最小値を出力すれば良い．

別解

点と直線の距離の公式

点と直線の距離の公式を覚えていればそれが使える．

ベクトル演算1

かなりラクになる．公式を覚えておく必要もない．

現在地を$\boldsymbol{x}_{0} = (x_{0}, y_{0})$，2頂点を$\boldsymbol{x}_{1} = (x_{1}, y_{1})$，$\boldsymbol{x}_{2} = (x_{2}, y_{2})$とする．

\begin{aligned}
\boldsymbol{r}_{0} &= \boldsymbol{x}_{0} - \boldsymbol{x}_{2} \\
\boldsymbol{r}_{1} &= \boldsymbol{x}_{1} - \boldsymbol{x}_{2}
\end{aligned}

とする．つまり，片方の頂点を原点とする位置ベクトルで現在地を表したのが$\boldsymbol{r}_{0}$であり，もう一方の頂点を表したのが$\boldsymbol{r}_{1}$である．

点$\boldsymbol{x}_{0}$から辺に降ろした垂線の足の位置ベクトルは，辺への射影ベクトル

\begin{aligned}
\biggl(\boldsymbol{r}_{0} \cdot \frac{\boldsymbol{r}_{1}}{\|\boldsymbol{r}_{1}\|}\biggr)
\frac{\boldsymbol{r}_{1}}{\|\boldsymbol{r}_{1}\|}
\end{aligned}

で表される．

三平方の定理より，垂線の長さは

\begin{aligned}
\sqrt{\|\boldsymbol{r}_{0}\|^{2}
- \biggl(\boldsymbol{r}_{0} \cdot \frac{\boldsymbol{r}_{1}}{\|\boldsymbol{r}_{1}\|}\biggr)^{2}}
\end{aligned}

で求められる．

ベクトル演算2

記号を上と同じように定める．また，$r_{0} = \|\boldsymbol{r}_{0}\|$，$r_{1} = \|\boldsymbol{r}_{1}\|$と表す．

$\boldsymbol{r}_{0}$と$\boldsymbol{r}_{1}$のなす角を$\theta$とすれば，求める垂線の長さは$r_{0} \bigl| \sin\theta\bigr|$である．

$\sin\theta$は外積

\begin{aligned}
\| \boldsymbol{r}_{0} \times \boldsymbol{r}_{1} \|
= r_{0} r_{1} |\sin\theta|
\end{aligned}

で出てくることに気づけば，答えは

\begin{aligned}
r_{0} \bigl| \sin\theta\bigr|
&= \frac{r_{0} r_{1} \bigl| \sin\theta\bigr| }{r_{1}} \\
&=\frac{\| \boldsymbol{r}_{0} \times \boldsymbol{r}_{1} \|}{\|\boldsymbol{r}_{1}\|}
\end{aligned}

で計算できる（ベクトル演算1の結果を変形したもの）．