← 返回题目列表

AtCoder · joi2007ho_c

C. 最古老的遗址

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

最古の遺跡 - 原题 PDF 第 1 页
原题PDF第5页
最古の遺跡 - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
3                    最古の遺跡 


問題

  昔, そこには集落があり, 多くの人が暮らしていた. 人々は形も大きさも様々な建
物を建てた. だが, それらの建造物は既に失われ, 文献と, 遺跡から見つかった柱だけ
が建造物の位置を知る手がかりだった.
 文献には神殿の記述がある. 神殿は上から見ると正確に正方形になっており, その
四隅には柱があった. 神殿がどの向きを向いていたかはわからない. また, 辺上や内
部に柱があったかどうかもわからない. 考古学者たちは, 遺跡から見つかった柱の中
で, 正方形になっているもののうち, 面積が最大のものが神殿に違いないと考えた.
 柱の位置の座標が与えられるので, 4 本の柱でできる正方形のうち面積が最大のも
のを探し, その面積を出力するプログラムを書け. なお, 正方形の辺は座標軸に平行
とは限らないことに注意せよ.


例

 下の図の例では, 10 本の柱があり, 座標(4, 2), (5, 2), (5, 3), (4, 3) にある4 本と座
標(1, 1), (4, 0), (5, 3), (2, 4) にある4 本が正方形をなしている. 面積が最大の正方形
は後者で, その面積は10 である.

            6y





             O                        x-


入力

 入力ファイルのファイル名はinput.txt である.
  1 行目には, 遺跡から見つかった柱の本数n が書かれている.

                        問題3-1

2 行目からn + 1 行目までのn 行の各々には, 柱のx 座標とy 座標が空白区切り
で書かれている.
  1 本の柱が2 度以上現れることはない.
  n は1 ≦n ≦3000 を満たす整数であり, 柱のx 座標とy 座標は0 以上5000 以
下の整数である.
 採点用データのうち, 配点の30% 分は1 ≦n ≦100 を満たし, 配点の60% 分は
1 ≦n ≦500 を満たす.


出力

 出力ファイルのファイル名はoutput.txt である.
 出力ファイルには1 個の整数を出力する. 4 本の柱からなる正方形が存在する場
合は, そのような正方形のうち面積が最大のものの面積を出力し, そのような正方形
が存在しない場合は0 を出力せよ.


入出力の例

 例に対応する入出力は以下の通りである.
input.txt

     10
     9 4
     4 3
     1 1
     4 2
     2 4
     5 8
     4 0
     5 3
     0 5
     5 2

output.txt

     10





                        問題3-2