きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 130:F - Minimum Bounding Box

問題

atcoder.jp

解法

x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい.なぜならば,変化するタイミング間では求める面積は広義単調増加・減少になるので,間ではなく両端のタイミングでその区間での面積の最大・最小となっているから.このタイミングは,左右それぞれに動くもののうち x 座標が最大・最小となる点同士,上下それぞれに動くもののうち y 座標が最大・最小となる点同士がぶつかるときになる.また,それぞれ x, y 座標が固定であるもののうち x, y 座標がそれぞれ最大・最小である点ともぶつかるときの面積も調べる必要がある.O(N).

解答

atcoder.jp

f:id:babcs2035:20190712145129p:plain