Codeforces #243 Div1 D. Sereja and Squares

うーん、これ定番問題なのかな。
http://codeforces.com/contest/425/problem/D

問題

２次元座標上、(0,0)-(10^5,10^5)の範囲でN個の格子点が与えられる。
軸に平行な辺をもつ正方形で、各点がN個に含まれるようなものは何個作れるか。

解法

正方形中の決まった２点、たとえば下辺を成す２点を決めればあと２点の位置が決まり、それらの存在判定はO(logN)で行える。

問題は２点を定めることで、何も考えないとO(N^2)通り候補ができてしまいTLEする。

そこで、各頂点をX座標同士およびY座標同士グループ化する。
そして各頂点を正方形の左下の点候補として総当たりする。
左下の点候補に対して２点目を決める必要があるが、同じX座標の点と同じY座標の点のうち少ない方を選び、２点目の総当たりを行う。

この手法だと、一部の点では２点目がO(N)近く候補が現れるが、大概のケースで候補がずっと小さくなる。
最も多いケースでも、N個の点を√Nの正方形状に配置した場合で、２点の組み合わせはO(N√N)である。
よって全体でO(N√N*logN)でなんとか間に合う。

int N;
int X[100001],Y[100001];
vector<int> XX[100002],YY[100002];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		XX[X[i]].push_back(Y[i]);
		YY[Y[i]].push_back(X[i]);
	}
	FOR(i,100001) sort(XX[i].begin(),XX[i].end());
	FOR(i,100001) sort(YY[i].begin(),YY[i].end());
	
	int ret=0;
	FOR(i,N) {
		if(XX[X[i]].size()<YY[Y[i]].size()) {
			FOR(x,XX[X[i]].size()) if(XX[X[i]][x]>Y[i]) {
				l=XX[X[i]][x]-Y[i];
				if(binary_search(XX[X[i]+l].begin(),XX[X[i]+l].end(),Y[i]) &&
				   binary_search(XX[X[i]+l].begin(),XX[X[i]+l].end(),Y[i]+l)) ret++;
			}
		}
		else {
			FOR(y,YY[Y[i]].size()) if(YY[Y[i]][y]>X[i]) {
				l=YY[Y[i]][y]-X[i];
				if(binary_search(XX[X[i]].begin(),XX[X[i]].end(),Y[i]+l) &&
				   binary_search(XX[X[i]+l].begin(),XX[X[i]+l].end(),Y[i]+l)) ret++;
			}
		}
	}
	cout << ret << endl;
}

まとめ

上位陣でこの解き方をさらっと書いてる人が結構いて、定番ネタなのかと思った。
O(N√N*logN)とは珍しい計算量だね。