CSAcademy Round #53 : D. Parallel Rectangles

この問題、考えたことあったけどO(N^2)解しか思いつかなかったんだよな。
https://csacademy.com/contest/round-53/task/parallel-rectangles/

問題

２次元座標上でN個の異なる格子点の座標が与えられる。
このうち４つを結んでできる長方形で、４辺が軸に平行なものは何通りか。

解法

平方分割の要領で解く。
各X座標において、何個点があるかで処理を分けよう。

• X座標がaである点がある程度以上多い場合
  • 他のX座標bをすべて探索し、(a,y),(b,y)両方に点があるようなyの数cを求めよう。(a,b)の対に対しc中2個選ぶ選び方の分だけ長方形が作れる。
  • なお、X座標がbである点も多い場合(a,b)と(b,a)で二重カウントしないように注意。
• X座標がaである点がある程度以上少ない場合
  • X座標がaである点のうち、y座標の対を数え上げよう。例えば(a,y1)(a,y2)があるならmap[(y1,y2)]++というように数え上げる。
  • 全X座標について処理が終わったとき、map[(y1,y2)]が２以上なら、map[(y1,y2)]個から２つのX座標(x1,x2)を選択することで、Y座標がy1,y2であるような４つの格子点を選ぶことができる。

int N;
vector<int> X[201010];
int C[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		X[x-1].push_back(y-1);
	}
	FOR(i,100000) {
		if(X[i].size()==1) X[i].clear();
		sort(ALL(X[i]));
	}
	
	ll ret=0;
	int S=40;
	map<pair<int,int>,int> M;
	FOR(i,100000) {
		if(X[i].size()>S) {
			FORR(c,X[i]) C[c]++;
			FOR(j,100000) if(j!=i && X[j].size()>=2) {
				int cnt=0;
				FORR(c,X[j]) cnt+=C[c];
				ret+=1LL*cnt*(cnt-1)/2;
			}
			FORR(c,X[i]) C[c]--;
			X[i].clear();
		}
		else {
			FOR(y,X[i].size()) FOR(x,y) M[{X[i][x],X[i][y]}]++;
		}
	}
	
	FORR(r,M) ret+=1LL*r.second*(r.second-1)/2;
	cout<<ret<<endl;
	
}

まとめ

うーん。