kmjp's blog

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

CSAcademy Round #34 : E. Point in Kgon

手間取ったけど定番っぽそう。
https://csacademy.com/contest/round-34/task/point-in-kgon/

問題

2次元座標上で、凸N角形と、内部の点Pが与えられる。
N角形からK個の点を選ぶとき、Pが内部に入るのは何通りか。

解法

Comb(N,K)からPが内部に入らない場合を引こう。
K角形がPの外側にあるとき、Pから見て一番右側の頂点vを総当たりしよう。

vを定めると、残り(K-1)個の頂点wはベクトルPvとベクトルPwの成す角が反時計回りに180度以内でなければならない。
逆にそのような頂点がf(v)個あれば、vに対しComb(f(v),K-1)通り対応する多角形が考えられる。
f(v)は尺取り法の要領で求めれば平均O(1)で求められるので、全体でO(N)で解ける。

int N,K;
ll X[201010],Y[201010];
ll PX,PY;
ll ret=0;

ll mo=1000000007;
ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>X[i]>>Y[i];
	cin>>PX>>PY;
	FOR(i,N) {
		X[i]-=PX;
		Y[i]-=PY;
		X[i+N]=X[i];
		Y[i+N]=Y[i];
	}
	ll ret=combi(N,K);
	int R=0;
	for(int L=0;L<N;L++) {
		R=max(R,L+1);
		while(R<L+N && X[L]*Y[R]-Y[L]*X[R]>=0) R++;
		ret += mo-combi(R-L-1,K-1);
	}
	cout<<ret%mo<<endl;
	
}

まとめ

どっかで見てそうだな…。