问题 3440 --遗址

3440: 遗址

题目描述

  很久很久以前有一座寺庙,从上往下看寺庙的形状正好是一个正方形,在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了,只在地上留下圆形的痕迹,可是现在地上有很多这样的痕迹,专家说一定是最大的那个。
       写一个程序,给出圆柱的坐标,找出由4个圆柱构成的最大的正方形,因为这就是寺庙的位置,要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。
       例如下图有10根柱子,其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形,(1,1),(4,0),(5,3),(2,4)也可以,后者是其中最大的,面积为10。

输入

第一行包含一个N(1<=N<=3000),表示柱子的数量。
接下来N行,每行有两个空格隔开的整数表示柱子的坐标(坐标值在0.到5000之间),柱子的位置互不相同。

输出

如果存在正方形,输出最大的面积,否则输出0。

样例输入输出

输入#1 复制
10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2
输出#1 复制
10

提示

数据范围
对于 30%的数据满足:1<=n<=100; 
对于 60%的数据满足:1<=n<=500; 
对于 100%的数据满足:1<=n<=3000。

序号 标题 作者 发表时间 费用 订购数 操作