kmjp's blog

競技プログラミング参加記です

Codeforces #574 Div2 F. Geometers Anonymous Club

こういう幾何の問題は珍しいかも?
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;
	
}

まとめ

多角形の合成に関する条件は覚えておくと応用が効きそうね。