AtCoder ABC #211 : F - Rectilinear Polygons

どうやると短く実装できるんだろうな。
https://atcoder.jp/contests/abc211/tasks/abc211_f

問題

軸に平行な辺を持つ単純な多角形がN個与えられる。
ここでQ個のクエリが与えられる。
各クエリでは座標が指定されるので、その座標がいくつの多角形に囲まれるかを答えよ。

解法

X軸順に平面走査することを考える。
BITを使い、多角形の頂点に遭遇するたびに、どのY座標の範囲が何個の多角形に囲まれるかを増減させ管理しよう。
クエリの座標に遭遇したら、BITを参照して、対応するY座標が何個の多角形に囲まれるかを返す。

あとは、多角形の頂点に対しBITをどう増減させるかだが、以下のように考えることができる。
多角形を周りに(進行方向右側が多角形の内側であるように)辺に沿って1周することを考える。
この時、右向きに移動する辺は、そのY座標以下の部分は多角形に含まれる(ので、BITでその範囲に1を加算する。)
左向きに移動する辺は、そのY座標以下の部分は多角形に含まれない(ので、BITでその範囲に1を減算する。)

int N;
int M;
vector<pair<int,int>> V;
vector<pair<int,int>> ev[201010];
int Q;
int X[202020],Y[202020],ret[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(x,N) {
		cin>>M;
		V.resize(M);
		
		int tar=0;
		FOR(j,M) {
			cin>>V[j].first>>V[j].second;
			V[j].first*=2;
			V[j].second*=2;
			if(V[j].first<V[tar].first) tar=j;
			else if(V[j].first==V[tar].first&&V[j].second>V[tar].second) tar=j;
		}
		
		rotate(V.begin(),V.begin()+tar,V.end());
		if(V[0].first==V[1].first) reverse(V.begin()+1,V.end());
		for(i=0;i+1<V.size();i+=2) {
			ev[V[i].first].push_back({V[i].second,-1});
			ev[V[i+1].first].push_back({V[i+1].second,1});
		}
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		X[i]=X[i]*2+1;
		Y[i]=Y[i]*2+1;
		ev[X[i]].push_back({i,Y[i]});
	}
	
	FOR(i,201010) {
		if(i%2==0) {
			FORR2(y,v,ev[i]) bt.add(y,v);
		}
		else {
			FORR2(i,y,ev[i]) ret[i]=bt(y);
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

右手周りかどうか判定するライブラリ作ろうかな…。