WUPC2012 F. 最後の問題

問題

2次元座標平面上に格子点がN個与えられる。
その中から4点選んで、長方形を作る。ただし、各辺は軸に平行でなければいけない。
このとき、長方形内部に点を含まないような長方形で最大の面積となるものの面積を返す。

考え方

N個の点から2点(x1,y1)と(x2,y2)選ぶと、(x1,y2)と(x2,y1)に点があるかどうかチェックするだけで、軸に平行な長方形を考えられる。
その長方形について、内部に点を持つかどうかは、2次元の部分和(累積和)((0,0)から(x,y)までに含まれる点の数を保持するdp)を前もって計算しておけば、O(1)で判定できる。