手間取ったけど定番っぽそう。
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; }
まとめ
どっかで見てそうだな…。