差分
このページの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 | ||
---|---|---|---|
行 186: | 行 186: | ||
最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外も全て包含するもの」に一致する。 | 最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外も全て包含するもの」に一致する。 | ||
- | * 3点を選ぶと、その3点の最小包含円は一意に決まる | + | * 3点を選ぶと、その3点の最小包含円は一意に決まる→それが他の点も包含する場合、これ以上大きくする必要は無い |
* 直角・鈍角三角形の場合は最長辺の中点 | * 直角・鈍角三角形の場合は最長辺の中点 | ||
* 鋭角三角形の場合は外接円 | * 鋭角三角形の場合は外接円 | ||
- | * 最小包含円は、任意の3点も当然包含せねばならない | + | * 最小包含円は、任意の3点も当然包含せねばならない→それより小さくならない |
よって、3点の組み合わせを列挙して、以下の計算を行えばよい。 | よって、3点の組み合わせを列挙して、以下の計算を行えばよい。 |