AtCoder ABC075D Axis - Parallel Rectangle
主に解説ACした問題とかで記録しておきたい問題を記録します。メモです。
https://atcoder.jp/contests/abc075/tasks/abc075_d
ABC075D Axis - Parallel Rectangle
400点。
概要：座標平面格子点上にN個の点が与えられる。長方形で四辺がx軸y軸とも平行かつ、辺を含む内部に与点N個中K個以上を含むもののうち、最小の面積を求めよ。
・Nが極端に小さく、逆に座標のrangeが巨大。
・最小の面積を実現するには長方形の四辺はすべてその辺中に「点」を含んでいるべきである。
よって、逆に言えば、
・考えられる長方形の四辺の組は「点を通って軸に平行」を満たす、たかだか50^4オーダー未満しか存在しない。
結局、長方形の四辺の候補を全探索すればよいことがわかる。
・ごちゃごちゃバグらせて30分ぐらいかかった。ダメ
・最初xとyをpairで持たせてたけどソートする必要がなければ無暗に紐づけるのは邪魔？
・細かいがgridとか数列の不等式はもうちょっときれいに書くのとテンプレ化したほうがよさそう
