TopCoder SRM 521 Div1 Medium RangeSquaredSubsets

なんか最近似た問題をDiv1 Easyで経験済みだったのですんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11577

問題

2次元座標上のN個の点(X[i],Y[i])が与えられる。
これらをnlow以上nhigh以下の正方形で囲むことを考える。
1つの正方形に含められる点集合は何通りあるか。

解法

登場するX座標およびY座標から、正方形が含むべき上端・下端・左端・右端を総当たりで求める。
これらの辺を含みつつ、その外側の辺を含まずに済むような正方形が作れるか判定したうえで、これらの4辺で囲める点の集合をbitmaskで管理すればよい。

4辺の総当たりがO(N^4)に点の内外判定を合わせてO(N^5)かかるが、N<=40なので問題ない。

class RangeSquaredSubsets {
	public:
	int N;
	pair<int,int> P[50];
	long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) {
		int i,x1,x2,y1,y2;
		vector<int> xx,yy;
		N=x.size();
		
		xx=x;
		yy=y;
		sort(xx.begin(),xx.end());
		sort(yy.begin(),yy.end());
		
		set<ll> S;
		FOR(x1,N) for(x2=x1;x2<N;x2++) FOR(y1,N) for(y2=y1;y2<N;y2++) {
			int ma=max(xx[x2]-xx[x1],yy[y2]-yy[y1]);
			ma=max(ma, nlow);
			if(ma>nhigh) continue;
			if(x1>0 && x2<N-1 && xx[x2+1]-xx[x1-1]<=ma) continue;
			if(y1>0 && y2<N-1 && yy[y2+1]-yy[y1-1]<=ma) continue;
			
			ll mask=0;
			FOR(i,N) if(x[i]>=xx[x1] && x[i]<=xx[x2] && y[i]>=yy[y1] && y[i]<=yy[y2]) mask |= 1LL<<i;
			if(mask) S.insert(mask);
		}
		
		return S.size();
	}
}

まとめ

これはすんなり。