mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ POJ 蟻本奴です。 問題 2187 -- Beauty Contest2 次元平面上に N 個の点が与えられる。最も遠い位置関係にある２つの頂点間の距離の二乗の値を求めよ。 解法 蟻本の p233 に書いてあるやつです。ふたつ目の解法でやりました。ひとつ目の解法では「凸包の頂点数は座標の幅の最大値 M に対して O()」って書いてあるけど全部同一直線上にあったら死なない？と思ってしまいましたが, 凸包では det の値が 0 "以下" だったら頂点を無視し続けるので, 同一直線上の点は無視するからやっぱり大丈夫ですね。ふたつ目の解法では, 最も遠い点対を凸包を回りながら走査していきます。 p, q … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F04%2F15%2F214758" title="POJ 2187: Beauty Contest - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%20%5Csqrt%7BM%7D Hatena Blog https://hatena.blog 2016-04-15 21:47:58 rich https://mayokoex.hatenablog.com/entry/2016/04/15/214758 1.0 100%