Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了，只在地

上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。

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

的边不一定平行于坐标轴。

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

，面积为10。

【数据范围】

30% 1<=N<=100

60% 1<=N<=500。

【输入格式】

第一行包含一个N(1<=N<=3000)，表示柱子的数量。

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

【输出格式】

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

Sample Input

10

9 4

4 3

1 1

4 2

2 4

5 8

4 0

5 3

0 5

5 2

Sample Output

10

【题目链接】:

【题解】

可以把正方形在图中分割成4个直角三角形(全等)和一个小的正方形.

则可以枚举正方形的底边的两个点(x1,y1),(x2,y2)

(一开始排个序,x坐标升序排一下,则x1< x2);

第三个点的坐标(x3,y3)

则

x2-x1=y3-y1

-(y2-y1)=x3-x1

同样的

x2-x1=y4-y2

-(y2-y1)=x4-x2

求出(x3,y3),(x4,y4)之后,看看这样的两个点是否存在,存在就尝试更新面积最大值;

面积就是边长的平方;sqr(x2-x1)+sqr(y2-y1);

【完整代码】

#include 
     
      #include 
      
       #define pii pair
       
        #define fi first#define se secondusing namespace std;const int MAXN = 5000+100;bool bo[MAXN][MAXN];int n,ans = 0;pii a[MAXN];int sqr(int x) { return x*x;}bool in(int x,int y){    if (x>5000) return false;    if (x<1) return false;    if (y>5000) return false;    if (y<1) return false;    return true;}int main(){    //freopen("F:\\rush.txt","r",stdin);    scanf("%d",&n);    for (int i = 1;i <= n;i++)    {        scanf("%d%d",&a[i].fi,&a[i].se);        bo[a[i].fi][a[i].se] = true;    }    sort(a+1,a+1+n);    for (int i = 1;i <= n-1;i++)        for (int j = i+1;j <= n;j++)        {            int dx = a[j].fi-a[i].fi;            int dy = a[j].se-a[i].se;            int y3 = a[i].se+dx,x3 = a[i].fi-dy;            int y4 = a[j].se+dx,x4 = a[j].fi-dy;            if (in(x3,y3)&&in(x4,y4) && bo[x3][y3]&&bo[x4][y4])                ans = max(ans,sqr(a[j].fi-a[i].fi)+sqr(a[j].se-a[i].se));        }    printf("%d\n",ans);    return 0;}