TopCoder SRM 521 Div2 Hard SquaredSubsets

定番問題っぽいが自前で解けずEditorialを参照。
http://community.topcoder.com/stat?c=problem_statement&pm=11438

問題

２次元座標中に配置されたP個の点の座標が与えられる。
ここにXY軸に平行な辺からなる１辺Nの正方形を配置したとき、内部に含まれた点集合の作り方の組み合わせを答えよ。
なお、正方形の頂点は格子点に限らなくても良い。

解法

最初X軸順にソートして走査かなーとか思ったけどうまくいかなかった。

各点からX軸Y軸に平行な直線を伸ばしてみると、最大でN本の横線と縦線ができ、(N+1)^2の領域に分けることができる。
ここから、２本の横線と２本の縦線を総当たりで選ぶことを考える。
これらの横線と縦線のうち、１辺Nの正方形で２本の横線・縦線を囲み、かつその外側の線を囲わずに済むかどうかを判定すると、その正方形に囲まれた頂点集合は答えの候補となる。

横線縦線の選び方がO(N^4)、頂点の正方形内内外判定がO(N)、囲まれた頂点をbitmaskで重複なく保持するのにsetを使ってO(logN)なので、全部でO(N^5 logN)。
実際は定数項が小さくなるので余裕で間にあう。

なお、Editorialに書かれた通り、横線縦線の選びかたをそれぞれO(N)で列挙することもできる。
これ以上左側の線を右に or 上側の線を下に動かすと、新たな線を囲いだすか、逆に囲んでた線が外れるような座標を選べばよい。
その場合O(N^3 logN)で処理することが可能。

class SquaredSubsets {
	public:
	
	long long countSubsets(int n, vector <int> x, vector <int> y) {
		int i,l,r,t,b;
		int N=x.size();
		vector<int> x2=x,y2=y;
		x2.push_back(-1<<29);
		x2.push_back(1<<29);
		y2.push_back(-1<<29);
		y2.push_back(1<<29);
		sort(x2.begin(),x2.end());
		sort(y2.begin(),y2.end());
		x2.erase(unique(x2.begin(),x2.end()),x2.end());
		y2.erase(unique(y2.begin(),y2.end()),y2.end());
		
		set<ll> bm;
		for(l=1;l<=x2.size()-2;l++) for(r=l;r<=x2.size()-2;r++) for(t=1;t<=y2.size()-2;t++) for(b=t;b<=y2.size()-2;b++) {
			if(x2[r]-x2[l]>n) continue;
			if(x2[r+1]-x2[l-1]<=n) continue;
			if(y2[b]-y2[t]>n) continue;
			if(y2[b+1]-y2[t-1]<=n) continue;
			
			ll mask=0;
			FOR(i,N) if(x[i]>=x2[l]&&x[i]<=x2[r]&&y[i]>=y2[t]&&y[i]<=y2[b]) mask |= 1LL<<i;
			if(mask) bm.insert(mask);
		}
		
		return bm.size();
	}
};

まとめ

定数項が小さければO(N^5 logN)でも行けるのね。
O(N^5)が行けるのはN<=36位までだと思ってたよ。