遗址

成绩 0 开启时间 2012年12月29日 星期六 10:25
折扣 0.8 折扣时间 2012年12月29日 星期六 10:25
允许迟交 关闭时间 2012年12月29日 星期六 10:25
输入文件 ruin.in 输出文件 ruin.out

 【题目描述】

很久很久以前有一座寺庙,从上往下看寺庙的形状正好是一个正方形,由4个角上竖立的圆柱搭建而成。现在圆柱都倒塌了,只在地上留下圆形的痕迹,可是现在地上有很多这样的痕迹,专家说一定是最大的那个。

    写一个程序,给出圆柱的坐标,找出由4个圆柱构成的最大的正方形,因为这就是寺庙的位置,要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。

    例如右上图有l0根柱子,其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形,(1,1),(4,O),(5,3),(2,4)也可以,后者是其中最大的,面积为l0。

【输入格式】

    第一行包含一个N(1≤N≤3 0 0 0),表示柱子的数量。

    接下来N行,每行有两个空格隔开的整数表示柱子的坐标(坐标值在0到5000之间),柱子的位置互不相同。

   

【输出格式】

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

【样例输入输出】

ruin.in

 ruin.out

 10

 9 4

 4 3

 1 1

 4 2

 2 4

 5 8

 4 0

 5 3

 0 5

 5 2

 10

 

 

 

 

 

 

 

 

 

 

 

【数据范围】

30%满足:1≤N≤100

60%满足:1≤N≤500

10%满足:1≤N≤3000