drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder400点 ABC-D 水色diff ギリギリ 最適化の考察：端点のみを考える 最適化の考察：変形しても悪化しない 二次元平面上のN点の問題 二次元累積和 全探索 制約条件:長方形領域 最適化の考察：探索候補を絞る 計算幾何 WaveletMatrix 区間の長さの最大値または最小値を求める NoviSteps1Q 古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考えます。 そのような長方形の面積の最小値を求めてください。 制約 考えたこと 一見手のつけづらい問題だけど、この手の幾何の問題で考えるべきことは「ギリギリを考える」ということだ。 たとえばある長方形が、その内部に 個以上の点を含むとする。このとき、この長方形を少しずつ縮めて、それらの点がちょうど長方形の周上に引っかかるところまで縮めてもよいことがわ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F07%2F27%2F175600" title="AtCoder ABC 075 D - Axis-Parallel Rectangle (1Q, 水色, 400 点) - けんちょんの競プロ精進記録" 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 2021-07-27 17:56:00 rich https://drken1215.hatenablog.com/entry/2021/07/27/175600 1.0 100%