AT_wupc2012_6 最後の問題

[problemUrl]: https://atcoder.jp/contests/wupc2012/tasks/wupc2012_6 いよいよコンテスト当日，僕は早稲田大学・西早稲田キャンパスに到着した．しかも，到達時間は4でも7でも割り切れる数字であった．とても縁起がいい．今ならどんな問題だって解ける気がする． 会場の教室には既に数十名の学生が集まっていた．運営チームがジャッジシステム，AtCoderの説明を終え，もうあと数分でコンテストが始まろうとしているところだった．僕は持ってきたノートブック型計算機を広げ，高鳴る心臓を抑えつつコンテストに備える． *(それでは，始めてください！)* そして，コンテストが始まった． 挑戦はどんな結果だったのか，そして，コンテストを通じて僕は何を得たのだろうか… しかし，これはまた別の話．機会があれば語ることにしよう．ところで，このコンテストに出題された最後の問題は，次のようなものであった． 二次元の座標平面上に格子点が $ N $ 個与えられる．それらの点の中から $ 4 $ 点を選んで長方形を作る時，その最大面積を求めるプログラムを作成せよ．ただし，長方形は以下の条件を満たす必要がある． - 長方形の各辺は $ x $ 軸または $ y $ 軸と並行になっていなければならない． - 長方形の内部(辺は含まない)に他の点を含んではならない． 長方形を構成する4点以外の点が辺の上にある時は，内部にはないと考えるものとする．また，条件を満たす長方形が一つも作れない時は，$ 0 $ を出力してほしい． 入力は以下の形式で標準入力から与えられる． > $ 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 $ を満たす．

N/A

N/A