Python｜最長増加部分列（LIS）を求める方法とその１つを再構成する方法
Aru
Aru's テクログ（Aruaru0）
点と線分の最短距離を計算する方法｜Pythonコード付き
Aru
Pythonを使って、点と線分の最短距離を計算する関数を作成します。本記事では、『アルゴリズム×数学が基礎からしっかり身につく本』に掲載されているアルゴリズムをベースに実装を行いました。
はじめに
競技プログラムでたまに必要になる「点と線分の距離計算」ですが、毎回考えるのが面倒なので関数化してみました。実装はできるけど、考えるのが少し面倒なものはライブラリ化しておくと便利です。
その他のAtCoderに役立つ記事の一覧
点と線分の最短距離の求め方
点と線分の最短距離を求める方法としては、「線分上のベクトルと点から線分への垂線が交わる点を求めてから計算する方法」がメジャーですが、この記事では、「アルゴリズム×数学が基礎からしっかり身につく本」のP.135の方法をベースにPythonの関数を作成します（※詳しいアルゴリズムを知りたい方は書籍を確認してください）。
簡単なアルゴリズムの説明
点をA、線分をBCとする。ここで角度で３つのパターンに分割して考えます。
- $\angle ABC > 90度$
$\angle ABC$が90度より大きい場合は、点Aと点Bの距離が最短 - $\angle ACB > 90度$
$\angle ABC$が90度より大きい場合は、点Aと点Cの距離が最短 - 上記以外
点Aと線分BCの最短距離は線分BCのどこか
（１）（２）の判定は、線分BA（CA）,BC（CB）の内積が０より小さいかどうかで判定できます。
（３）の場合の最短距離の求め方ですが、「ベクトルBCとベクトルBAが作る平行四辺形の面積と外積が一致する」という性質を利用します。
平行四辺形の面積Sがわかれば、平行四辺形の面積は底辺×高さなので、底辺をBCとすれば高さはAまでの最短距離に一致します。
（１）（２）（３）のパターンの距離計算方法がわかったので実装します。
Pythonで関数を作成
関数calc_dist(dot, line)
ベクトルを作る計算が結構あるのでcalc_vector関数も用意しました。この関数は、点dotと線分lineの最短距離を求める関数calc_distの中で利用しています。
calc_distの中身は先ほど説明したアルゴリズムをそのまま実装しました。
def calc_vector(x0, y0, x1, y1) :
return x1-x0, y1-y0
def calc_dist(dot, line):
ax, ay = dot
bx, by, cx, cy = line
BAx, BAy = calc_vector(bx, by, ax, ay)
BCx, BCy = calc_vector(bx, by, cx, cy)
CAx, CAy = calc_vector(cx, cy, ax, ay)
CBx, CBy = calc_vector(cx, cy, bx, by)
if BAx * BCx + BAy * BCy < 0 :
return (BAx * BAx + BAy * BAy)**0.5
if CAx * CBx + CAy * CBy < 0 :
return (CAx * CAx + CAy * CAy)**0.5
s = abs(BAx * BCy - BAy * BCx)
l = (BCx*BCx + BCy * BCy)**0.5
return s/l使い方
点(ax, ay)と、線分(bx, by)-(cx, cy)の最短距離を求める場合は、以下のように呼び出します。
点と線分は、()で括って入力しています。この入力にしたのは、x0, y0, x1, y2, x2, y2みたいな引数だと、x0, x1が点だったからx2, y2が点の入力だったかを間違える可能性があるからです（こういうところでミスしたくないので、引数をちょっと工夫しました）
dist = calc_dist((ax, ay), (bx, by, cx, cy))終わりに
本当にたまにしか使わないのですが、使う時は悩むので関数を作ってみました。毎回、他言語の実装をPythonに移植したり、数式からコードを起こしたりしていましたが、この手の処理は、関数ライブラリみたいな形で用意しておくとAtCoderなどでは便利です。Myライブラリは作っておくと良いと思います。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
