差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0112_abc151 [2020/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0112_abc151 [2020/01/12] (現在) – [解法] ikatakos | ||
|---|---|---|---|
| 行 24: | 行 24: | ||
| よって、道である各マスをスタート地点として全て試し、最長移動距離の最大値が答え。 | よって、道である各マスをスタート地点として全て試し、最長移動距離の最大値が答え。 | ||
| - | $H,W$ の上限が小さいので、1回の探索で多くとも400、400個の各マスをスタート地点としても、160000回に比例する計算量で間に合う。 | + | $H,W$ の上限が小さいので、スタート地点候補が最大400、1回の探索で探索するマスが最大400、あわせて160000回に比例する計算量で間に合う。 |
| なお、木の直径を求めるように「適当な1マスから最遠点を求める」→「そこからの最遠点を求める」方法だと、ループがある場合は最適が保証されない。 | なお、木の直径を求めるように「適当な1マスから最遠点を求める」→「そこからの最遠点を求める」方法だと、ループがある場合は最適が保証されない。 | ||
| 行 184: | 行 184: | ||
| PythonではOpenCVを非常に使いたくなるところだが、残念ながら入っていない。 | PythonではOpenCVを非常に使いたくなるところだが、残念ながら入っていない。 | ||
| - | 最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外を全て包含するもの」に一致する。 | + | 最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外も全て包含するもの」に一致する。 |
| * 3点を選ぶと、その3点の最小包含円は一意に決まる | * 3点を選ぶと、その3点の最小包含円は一意に決まる | ||
| * 直角・鈍角三角形の場合は最長辺の中点 | * 直角・鈍角三角形の場合は最長辺の中点 | ||
| * 鋭角三角形の場合は外接円 | * 鋭角三角形の場合は外接円 | ||
| + | * →これが他の点も包含する場合、それ以上大きくする必要は無い | ||
| * 最小包含円は、任意の3点も当然包含せねばならない | * 最小包含円は、任意の3点も当然包含せねばならない | ||
| + | * →それより小さくならない | ||
| よって、3点の組み合わせを列挙して、以下の計算を行えばよい。 | よって、3点の組み合わせを列挙して、以下の計算を行えばよい。 | ||
