こういう幾何の問題は珍しいかも?
https://codeforces.com/contest/1195/problem/F
問題
N個の2次元座標上に配置された多角形が与えられる。
2つの多角形を合成するとは、1つ目の多角形内の位置ベクトルaと2つ目の多角形内の位置ベクトルbに対し、c=a+bの通ることができる領域である多角形を生成することである。
3つ以上の多角形を合成する場合、上記手続きを繰り返し1つずつ追加していく。
以下のクエリに答えよ。
- L番目からR番目の多角形を合成したとき、何角形になるか。
解法
多角形を合成する際、基本的には両者の頂点数を足した多角形ができるが、もし両者が同じ向きの辺をもつ場合、合成してもそれらは点を増やさない。
よって、(合成する多角形の頂点数の総和)-sum(同じ向きの辺の数-1)が解となる。
クエリを並べ替え、尺取り法で解いていこう。
前者はBITでも累積和でもよく、後者は事前に辺の向きに番号を振って、同じ向きの辺の数を数えていけばよい。
int N,Q; 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; vector<pair<int,int>> V[101010]; vector<int> nex[101010]; map<pair<int,int>,int> M; int L[101010],R[101010]; vector<int> ev[101010]; int ret[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x; vector<pair<int,int>> P(x); FOR(j,x) cin>>P[j].first>>P[j].second; P.push_back(P[0]); FOR(j,x) { int dx=P[j+1].first-P[j].first; int dy=P[j+1].second-P[j].second; int g=__gcd(abs(dx),abs(dy)); V[i].push_back({dx/g,dy/g}); } } for(i=N-1;i>=0;i--) { FORR(v,V[i]) { if(M.count(v)) { nex[i].push_back(M[v]); } else { nex[i].push_back(N); } M[v]=i; } } FORR(m,M) bt.add(m.second,1); cin>>Q; FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--; ev[L[i]].push_back(i); } FOR(i,N) { FORR(e,ev[i]) ret[e]=bt(R[e]-1)-bt(i-1); FORR(e,nex[i]) bt.add(e,1); } FOR(i,Q) cout<<ret[i]<<endl; }
まとめ
多角形の合成に関する条件は覚えておくと応用が効きそうね。