WUPC 2012

F - 最後の問題


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

 いよいよコンテスト当日,僕は早稲田大学・西早稲田キャンパスに到着した.しかも,到達時間は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 点を選び長方形を作ることができる.辺上には他の点が重なっていても良いことに注意せよ.

Submit提出する