#abc075d. [abc075_d]Axis-Parallel Rectangle
[abc075_d]Axis-Parallel Rectangle
問題文
2次元座標上に 個の点があります。
番目の点の座標は です。
長方形の内部に 点のうち 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。
制約
- 入力値はすべて整数である。(21:50 追記)
入力
入力は以下の形式で標準入力から与えられる。
出力
条件を満たす長方形の中で最小面積となるような長方形の面積を出力せよ。
入力例 1
4 4
1 4
3 3
6 2
8 1
出力例 1
21
条件を満たす最小面積となる長方形の つは の つの頂点で構成されます。
その面積は であるため、 と出力します。
入力例 2
4 2
0 0
1 1
2 2
3 3
出力例 2
1
入力例 3
4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999
出力例 3
3999999996000000001
オーバーフローに注意してください。