TopCoder SRM 521 Div1 Medium RangeSquaredSubsets

問題

m個の点が与えられる。
これらの点の空でない部分集合Pで、Pに属する点を全て含み、Pに属さない点は全く含まないような、軸に平行なnxnの正方形が存在するようなPをn-squaredと呼ぶ。


nlow以上nhigh以下なsquaredな部分集合の数を求めよ。

制約条件

点の座標の絶対値≦10^8
点の数≦50

方針

正方形の辺の位置を決めてから、実際にそのような位置に正方形が存在するかを調べる。


左側の辺の区間を(x[i-1],x[i] ]
右側の辺の区間を[x[j],x[j+1])
上側の辺の区間を(y[k-1],y[k] ]
下側の辺の区間を[y[l],y[l+1])にあるように定めると、


実際に正方形が存在するならば、辺の長さはx[j]-x[i]とys[l]-ys[k]の長いほう以上であり、
y[l+1]-y[k-1]-1とxs[j+1]-xs[i-1]-1の短いほう以下である。
この範囲にnlow以上nhigh以下の整数が存在するかを見ればよい。

ソースコード

int nl,nh;
vi xs,ys;
bool can(int xl,int xr,int yl,int yh){
	int N=max(xs[xr]-xs[xl],ys[yh]-ys[yl]);
	N=max(N,nl);
	int h=ys[yh+1]-ys[yl-1]-1, w=xs[xr+1]-xs[xl-1]-1;
	return N<=min(w,h)&&N<=nh;
}

class RangeSquaredSubsets {
	public:
	long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) 
	{
		nl=nlow; nh=nhigh;
		xs.clear(); ys.clear();
		
		int n=x.size();
		xs.pb(-(int)1e9); xs.pb((int)1e9);
		ys.pb(-(int)1e9); ys.pb((int)1e9);
		rep(i,n)xs.pb(x[i]), ys.pb(y[i]);
		sort(all(xs)); sort(all(ys));
		xs.erase(unique(all(xs)),xs.end()); ys.erase(unique(all(ys)),ys.end());
		
		set<ll> ans;
		rep(j,xs.size()-1)for(int i=1;i<=j;i++)
		rep(l,ys.size()-1)for(int k=1;k<=l;k++)if(can(i,j,k,l)){
			ll bit=0;
			rep(m,n)if(xs[i]<=x[m]&&x[m]<=xs[j]&&ys[k]<=y[m]&&y[m]<=ys[l])bit|=1ll<<m;
			ans.insert(bit);
		}
		ans.erase(0);
		return ans.size();
	}
};