kmjp's blog

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

Codeforces #313 Div1 D. Randomizer

これはすっかり頭から抜けていた定理だった。
http://codeforces.com/contest/559/problem/D

問題

2次元座標上でN個の異なる格子点Piが与えられる。
これらの格子点を反時計回りに結ぶと、凸多角形になる。

このうち一部の頂点を選び、凸多角形にするようにする。
その際、凸多角形を生成できる点の選び方のうち、各凸多角形は等確率で選択されるとする。
多角形内に存在する格子点の数の期待値を求めよ。

解法

ピックの定理を用いて解く。

Nが多いとき、各頂点が選ばれる確率は1/2に近い。
よって、概ね元の多角形に近い面積多角形が選択されることが期待できる。
この考察の元に、まず元の多角形内の格子点数を求めたうえで、ある格子点が多角形に含まれない確率を求めよう。
格子点のカウント自体は多角形の面積と辺上の格子点の数からピックの定理で求められる。

点P[i]とP[i+x] (mod Nは以下略)が多角形の1辺を無し、かつP[i+1]~P[i+x-1]がいずれも多角形に選択されないケースを考える。
この場合、P[i]-P[i+x]を結んだ辺上、及びP[i]~P[i+x]に囲まれた格子点は、選択後の多角形に含まれない。
あとはこのような点の選び方が成される確率が分かれば、上記含まれない格子点の数と掛け合わせて全体の格子点数から引けばよい。

全体の多角形の数は、点を3つ以上選ぶ選び方なので 2^N - {}_N C_0 - {}_N C_1 - {}_N C_2 = 2^N - (1+N+\frac{N(N-1)}{2})である。
「点P[i]とP[i+x]が多角形の1辺を無し、かつP[i+1]~P[i+x-1]がいずれも多角形に選択されないケース」の数は、そのうちP[i]~P[i+x]の選ばれる/選ばれないパターンは決まっていて、P[i+x+1]~P[i-1]は1個以上が選ばれる確率なので、 2^{N-(x+1)} - 1である。
よって確率は \frac{2^{N-(x+1)} - 1}{2^N - (1+N+\frac{N(N-1)}{2})}となる。
このまま計算すると2^Nが大きくなるので、分子分母から2^Nを割ると、 \frac{2^{-(x+1)} - 2^{-N}}{1 - (1+N+\frac{N(N-1)}{2})*2^{-N}}となる。

ここで、xが十分大きい、たとえば60以上の場合、分子は2^-60となり誤差の範囲内になる。
よって、P[i]とP[i+x]の組み合わせは、iはN個全通り試す必要があるが、xは60程度まで試せば十分である。

int N;
ll X[201010],Y[201010],P[202020];
ll ssum2;
ll border;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i], X[i+N]=X[i], Y[i+N]=Y[i];
	FOR(i,N) ssum2 += X[i]*Y[i+1]-Y[i]*X[i+1];
	FOR(i,N) {
		P[i+N]=P[i]=__gcd(abs(X[i+1]-X[i]),abs(Y[i+1]-Y[i]));
		border+=P[i];
	}
	
	long double inp=(abs(ssum2)-border+2)/2;
	long double pox[105];
	long double pon=pow(0.5,N);
	FOR(i,100) pox[i]=pow(0.5,i+1);
	
	FOR(i,N) {
		ll tsum2=0, tb=0;
		for(x=1;x<min(N,80);x++) {
			long double prob=(pox[x]-pon)/(1-(1+N+N*(N-1)/2)*pon);
			if(prob<1e-20) continue;
			
			tsum2 += (X[i+x]-X[i])*(Y[i+x-1]-Y[i])-(Y[i+x]-Y[i])*(X[i+x-1]-X[i]);
			tb += P[i+x-1];
			if(x==1) continue;
			
			ll pb=__gcd(abs(X[i+x]-X[i]),abs(Y[i+x]-Y[i]));
			inp -= prob*(pb-1);
			pb+=tb;
			ll inpt=(abs(tsum2)-pb+2)/2;
			inp -= prob*inpt;
		}
	}
	_P("%.12lf\n",(double)inp);
}

まとめ

ピックの定理をすっかり忘れていたので面白かったし、誤差の関係である程度以上のxは無視できるというのも珍しい考え方だった。