题面
很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由4个角上竖立的圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。
写一个程序，给出圆柱的坐标，找出由4个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。
注意正方形的边不一定平行于坐标轴。 例如图有l0根柱子，其中(4，2)，(5，2)，(5，3)，(4，3)可以形成一个正方形，(1，1)，(4，O)，(5，3)，(2，4)也可以，后者是其中最大的，面积为l0
对于 30%的数据满足： 1<=n<=100；
对于 60%的数据满足： 1<=n<=500；
对于 100%的数据满足： 1<=n<=3000。
分析
我，数学硬伤本人，考试的时候大家都是90,100，就我60分。
当时想的是，枚举线，就看哪些线的距离相等，并且满足四个点中，对点横坐标之和等于纵坐标之和，但是复杂度确实高，本来3000都是比较艰辛地过N2
正解其实是利用全等，然后就可以通过两个点推出另外两个点的坐标，就是枚举两个点的效率，在此不再证明。
正方形其实是可以往上斜和往下斜的两种。
设坐标之差是
dx=abs(x1-x2),dy=abs(y1-y2);
两种情况分别是
x3=x2+dy,y3=y2+dx,x4=x1+dy,y4=y1+dx;
x3=x2+dy,y3=y2-dx,x4=x1+dy,y4=y1-dx;
代码
60分
#include<bits/stdc++.h> using namespace std; #define N 3010 struct email { int x,y; }a[N]; struct line { int d; email p; }b[N]; int n,ans,maxx; map<pair<int,int>,bool>exist; inline int dis(email a,email b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } bool cmp(line x,line y) { return x.d>y.d; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); exist[make_pair(a[i].x,a[i].y)]=true; } for(int i=1;i<=n;i++) { memset(b,0,sizeof(b)); for(int j=i+1;j<=n;j++) b[j].d=dis(a[i],a[j]),b[j].p=a[j]; sort(b+1,b+1+n,cmp); int k=1,maxx=0; while(k<n) { if(b[k].d==0)break; int num=0,o=k; while(b[k].d==b[k+1].d) num++,k++; k=o; for(int j=k;j<=k+num;j++) for(int z=j+1;z<=k+num;z++) { email j1=b[j].p,z1=b[z].p; int xx=j1.x+z1.x-a[i].x,yy=j1.y+z1.y-a[i].y; if(xx==a[i].x&&yy==a[i].y)continue; if(exist[make_pair(xx,yy)]) maxx=b[j].d; } if(maxx)break; k++; } ans=max(ans,maxx); } printf("%d ",ans); return 0; }
100分
用map会t,改成二维数组过了
#include<bits/stdc++.h> using namespace std; #define N 5010 int exist[N][N]; struct email { int x,y; }a[N]; int n,ans,maxx; inline int read(int &ret) { int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();} return ret*f; } inline int dis(email a,email b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } inline int check(int x,int y) { if(x<0||x>5000||y<0||y>5000||exist[x][y]==false) return 0; else return 1; } int main() { read(n); for(int i=1;i<=n;i++) { read(a[i].x);read(a[i].y); exist[a[i].x][a[i].y]=1; } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { int x1=a[i].x,x2=a[j].x,y1=a[i].y,y2=a[j].y; int dx=abs(x1-x2),dy=abs(y1-y2); int x3=x2+dy,y3=y2+dx,x4=x1+dy,y4=y1+dx; if(check(x3,y3)&&check(x4,y4)) ans=max(ans,dis(a[i],a[j])); x3=x2+dy,y3=y2-dx,x4=x1+dy,y4=y1-dx; if(check(x3,y3)&&check(x4,y4)) ans=max(ans,dis(a[i],a[j])); } printf("%d ",ans); return 0; }