aoj0518:The Oldest Site

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0518

解法

　まず、最も単純な解法として四重ループを回すというものが考えられる。この解法だとO(N^4)となり間に合わない。
　だが、正方形の4つの頂点のうち3つが決まれば残りの1つは一意に定まることが簡単にわかる。よって、三重ループで頂点を3つ選んで残りの1つの頂点の座標を計算し、そのような点が存在するかを二分探索で調べればよい。これでO(N^3logN)となる。しかしまだこれでも間に合わない。
　ここで、点を2つだけ決める。この2つの点をu,vとおく。すると、u,vを頂点とする正方形はuとvが対角の関係になるものを除けば2つしかない。さらに2つの正方形のうち、片方だけを調べればよい。なぜなら、もう片方は点v,uを選んだ時に調べるからである。よって、点を2つ決めれば調べるべき正方形は一意に定まるといってもよい。
　u,vを選んだ時の残り2つの頂点の座標は簡単に計算できるので、先程と同じように二分探索を用いれば存在するかどうか調べられる。これでO(N^2logN)となる。これで通る。

コード

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;

int N;
P ps[3000];

int f(int i,int j){
    int dx=ps[i].first-ps[j].first;
    int dy=ps[i].second-ps[j].second;

    if(!binary_search(ps,ps+N,P(ps[i].first+dy,ps[i].second-dx)))return 0;
    if(!binary_search(ps,ps+N,P(ps[j].first+dy,ps[j].second-dx)))return 0;
    return dx*dx+dy*dy;
}
void solve(){
    for(int i=0;i<N;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        ps[i]=P(x,y);
    }
    sort(ps,ps+N);
    int ma=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i==j)continue;
            ma=max(ma,f(i,j));
        }
    }
    printf("%d\n",ma);
}

int main(){
    while(scanf("%d",&N),N)solve();
    return 0;
}