AOJ 0518: The Oldest Site

点A(a,b)と点B(c,d)があるとき、a <= c && b < dのときだけ判定すれば、2重ループで全てのパターンを調べることができます。点が2つ定まった時にできる正方形は2通りだけありますが、少し考えれば片方だけ考慮すれば良いことが分かります。
A,Bを探すときは、入力された順に辿って行き、正方形ができているか調べるときは、辿らずに直接調べることで、O(n^2)になります。(全部辿るとO(n^4)になる)

#include<cstdio>
#include<cstring>
using namespace std;

int x[3000],y[3000],n,r;
bool g[5001][5001];

int main(){
	while(scanf("%d",&n),n){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(g,0,sizeof(g));
		int ans = 0;
		for(int i = 0; i < n; i++){
			scanf("%d%d",x+i,y+i);
			g[x[i]][y[i]] = 1;
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				int dx = x[j]-x[i],dy = y[j]-y[i],res = dx*dx+dy*dy;
				if(dx>=0 && dy>0 && res>ans && x[j]+dy<=5000 && y[i]-dx>=0 && g[x[i]+dy][y[i]-dx] && g[x[j]+dy][y[j]-dx])ans = res;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}