F - 最後の問題
Editorial
/
いよいよコンテスト当日,僕は早稲田大学・西早稲田キャンパスに到着した.しかも,到達時間は4でも7でも割り切れる数字であった.とても縁起がいい.今ならどんな問題だって解ける気がする.
会場の教室には既に数十名の学生が集まっていた.運営チームがジャッジシステム,AtCoderの説明を終え,もうあと数分でコンテストが始まろうとしているところだった.僕は持ってきたノートブック型計算機を広げ,高鳴る心臓を抑えつつコンテストに備える.
(それでは,始めてください!)
そして,コンテストが始まった.
挑戦はどんな結果だったのか,そして,コンテストを通じて僕は何を得たのだろうか… しかし,これはまた別の話.機会があれば語ることにしよう.ところで,このコンテストに出題された最後の問題は,次のようなものであった.
二次元の座標平面上に格子点が N 個与えられる.それらの点の中から 4 点を選んで長方形を作る時,その最大面積を求めるプログラムを作成せよ.ただし,長方形は以下の条件を満たす必要がある.
入力は以下の形式で標準入力から与えられる.
与えられた点を使って条件を満たすような長方形を作る時,その最大面積を一行に出力せよ.もし,条件を満たす長方形が一つも作れない場合は,0 を出力せよ.
なお,最後には改行を出力せよ.
100点満点中,10点分については,N ≦ 100 を満たす.
また,別の20点分については,N ≦ 1000 を満たす.


Time Limit: 5 sec / Memory Limit: 256 MB
会場の教室には既に数十名の学生が集まっていた.運営チームがジャッジシステム,AtCoderの説明を終え,もうあと数分でコンテストが始まろうとしているところだった.僕は持ってきたノートブック型計算機を広げ,高鳴る心臓を抑えつつコンテストに備える.
(それでは,始めてください!)
そして,コンテストが始まった.
挑戦はどんな結果だったのか,そして,コンテストを通じて僕は何を得たのだろうか… しかし,これはまた別の話.機会があれば語ることにしよう.ところで,このコンテストに出題された最後の問題は,次のようなものであった.
問題文
- 長方形の各辺は x 軸または y 軸と並行になっていなければならない.
- 長方形の内部(辺は含まない)に他の点を含んではならない.

図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 点の座標はすべて異なる.
出力
なお,最後には改行を出力せよ.
部分点
また,別の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 点を選び長方形を作ることができる.辺上には他の点が重なっていても良いことに注意せよ.