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