F - 最後の問題 Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

　いよいよコンテスト当日，僕は早稲田大学・西早稲田キャンパスに到着した．しかも，到達時間は4でも7でも割り切れる数字であった．とても縁起がいい．今ならどんな問題だって解ける気がする．
　会場の教室には既に数十名の学生が集まっていた．運営チームがジャッジシステム，AtCoderの説明を終え，もうあと数分でコンテストが始まろうとしているところだった．僕は持ってきたノートブック型計算機を広げ，高鳴る心臓を抑えつつコンテストに備える．

　(それでは，始めてください！)

　そして，コンテストが始まった．

　挑戦はどんな結果だったのか，そして，コンテストを通じて僕は何を得たのだろうか…　しかし，これはまた別の話．機会があれば語ることにしよう．ところで，このコンテストに出題された最後の問題は，次のようなものであった．

問題文

　二次元の座標平面上に格子点が N 個与えられる．それらの点の中から 4 点を選んで長方形を作る時，その最大面積を求めるプログラムを作成せよ．ただし，長方形は以下の条件を満たす必要がある．
    　
  • 長方形の各辺は x 軸または y 軸と並行になっていなければならない．
    • 　
  • 長方形の内部(辺は含まない)に他の点を含んではならない．
長方形を構成する4点以外の点が辺の上にある時は，内部にはないと考えるものとする．また，条件を満たす長方形が一つも作れない時は，0 を出力してほしい．
図1：条件を満たす長方形の例
図2：条件を満たさない長方形の例．長方形の辺は軸に並行でなければならない．
図3：条件を満たさない長方形の例．長方形の内部に他の点を含んではならない．

入力

入力は以下の形式で標準入力から与えられる． 
N
x_{1}　y_{1}
x_{2}　y_{2}
...
x_{i}　y_{i}
...
x_{N}　y_{N}
  • 1 行目に点の数を表す N(4 ≦ N ≦ 10000)が与えられる．
  • 2 行目〜N+1行目にはそれぞれの点の x 座標と y 座標が半角スペース区切りで与えられる．
  • 各 i について 0 ≦ x_{i} ≦ 999 かつ 0 ≦ y_{i} ≦ 999 を満たす．
  • N 点の座標はすべて異なる．

出力

与えられた点を使って条件を満たすような長方形を作る時，その最大面積を一行に出力せよ．もし，条件を満たす長方形が一つも作れない場合は，0 を出力せよ．
なお，最後には改行を出力せよ．

部分点

100点満点中，10点分については，N ≦ 100 を満たす．
また，別の20点分については，N ≦ 1000 を満たす．

入力例 1

4
0 0
1 0
0 1
1 1

出力例 1

1
  • 4 点を選んで長方形を作ることができ，その面積は 1 である．

入力例 2

5
0 0
2 0
0 2
2 2
1 1

出力例 2

0
  • (0,0),(0,2),(2,2),(2,0) の 4 点を選び長方形を作ることができるが，この長方形は内部に (1,1) を含んでいるため，条件を満たさない．与えられた 5 点だけでは条件を満たす長方形を作れないため，0 を出力する．

入力例 3

6
0 0
1 0
2 0
0 1
0 2
2 2

出力例 3

4
  • (0,0),(0,2),(2,2),(2,0) の 4 点を選び長方形を作ることができる．辺上には他の点が重なっていても良いことに注意せよ．