#P1959. 遗址

遗址

题目描述

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

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

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

输入格式

第一行包含一个 N(1N3000)N(1\leq N\leq 3000),表示柱子的数量。

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

输出格式

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

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

10

提示

【数据范围】

30%30\% 满足:1N1001\leq N \leq100

60%60\% 满足:1N5001\leq N \leq500

100%100\% 满足:1N30001\leq N \leq3000