kmjp's blog

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

TopCoder SRM 698 Div1 Medium IntersectingConvexHull

SRM

これは思いつかん。
https://community.topcoder.com/stat?c=problem_statement&pm=14357

問題

2次元座標上にあるN個の頂点がある。
これらは３つ以上同一直線上にあることはない。

これらの頂点群から２つの集合s1,s2を取る。
s1とs2は同じ頂点を含まない。また、s1とs2どちらにも含まれない頂点が合っても良い。

この時、s1の頂点群の凸包とs2の頂点群の凸包の共通部分の面積が正であるようなs1,s2の選び方は何通りあるか。

解法

まず、s1,s2は3個以上の頂点を含んでいないといけないので、s1,s2それぞれ3個以上の頂点を含む組み合わせのみ考える。
この組み合わせは \displaystyle \sum_{i=3}^N \sum_{j=3}^{i+j \le N} {}_N C_i \times {}_{N-i} C_j通りである。

ここから、共通部分を持たない組み合わせを引こう。
s1の凸包とs2の凸包が共通部分を持たないとする。
その時、u∈s1、v∈s2で、u-vを通る直線を引くと、この直線が両凸包とu,v以外で交わらないというような点の対(u,v)が1つだけある。
逆に考えると、２頂点の対(u,v)を定めると、そのような凸包の組み合わせが列挙できる。

u-vの直線に対し、残りの頂点をu→vに向かう向きに対して左側か右側かで分けよう。
L(u,v)を左側の頂点数、R(u,v)を右側の頂点数とすると、L(u,v)、R(u,v)から2個以上の頂点を取れば、互いに交わらず、u-vを結ぶ直線でu,v以外で交わらない２つの凸包を作ることができる。
L(u,v)個の頂点から2つの以上頂点を選ぶやり方は、L(u,v)個の頂点をそれぞれ選ぶ・選ばないの2^L(u,v)通りの組み合わせから0個または1個しか選ばないケースを引けばよい。
よって(u,v)に対し(2^L(u,v)-1-L(u,v))*(2^R(u,v)-1-R(u,v))を引いていけば数が求められる。

まとめると、u∈s1、v∈s2を総当たりし、L(u,v)、R(u,v)を求めて(2^L(u,v)-1-L(u,v))*(2^R(u,v)-1-R(u,v))の総和を求めれば、交差しない２つの凸包の組み合わせを求められる。
これを最初に求めた凸包の組み合わせから引けばよい。

class IntersectingConvexHull {
	public:
	
	int count(vector <int> x, vector <int> y) {
		ll mo=1000000007;
		ll C[110][110];
		ll p2[110];
		int N=x.size();
		int i,j,k;
		
		FOR(i,104) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		
		p2[0]=1;
		FOR(i,104) p2[i+1]=p2[i]*2%mo;
		
		ll ret=0;
		for(i=3;i<=N;i++) for(j=3;i+j<=N;j++) ret = (ret + C[N][i]*C[N-i][j])%mo;
		
		FOR(i,N) FOR(j,N) if(i!=j) {
			int num[2]={};
			FOR(k,N) if(i!=k && j!=k) num[(1LL*(x[i]-x[j])*(y[k]-y[j])-1LL*(y[i]-y[j])*(x[k]-x[j]))>0]++;
			if(num[0]<2 || num[1]<2) continue;
			
			ll a=p2[num[0]]-1-num[0];
			ll b=p2[num[1]]-1-num[1];
			
			ret = (ret-a*b%mo+mo)%mo;
		}
		return ret;
	}
}

まとめ

この数え上げは思いつかない。