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(); } };