mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AtCoder 問題 jag2016autumn.contest.atcoder.jp二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。 解法 蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します。上側の凸包を構成するのは, y 座標の上下を逆転させて下側の凸包を構成するのと同じようにできます。よって, 下側凸包を構成しながらそれぞれの凸包の面積を更新していく, というように計算すれば, O(N log N) で X 座標の左から見ていった下側凸包 X 座標の左から見ていった上側凸包(Y 座標を -1 倍す… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F09%2F11%2F125936" title="JAG 夏合宿 Day3 G - Share the Ruins Preservation - 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> Hatena Blog https://hatena.blog 2016-09-11 12:59:36 rich https://mayokoex.hatenablog.com/entry/2016/09/11/125936 1.0 100%