Codeforces 336B Vasily the Bear and Fly

問題

平面上に半径Rの円が2m個ある。
A1〜Amは中心が座標((2i - 1)R, 0)にあり、
B1〜Bmは中心が座標((2i - 1)R, 2R)にある。

円Aiの中心から円Bjの中心へ、2m個の円の内部または周だけを通って行くときの最短距離をd(i, j)とする。
全ての1≦i, j≦mに対するd(i, j)の平均値を求めよ。

制約条件

m≦10^5

方針

まずd(i, j) =
2*R (i = j)
2*√2 R (|i-j| = 1)
2*(|i-j| - 1 + √2)R (それ以外）
と表せる。

Σd(1, i)はO(m)で計算できる。これをs(1)とおく。
s(2) = Σd(2, i)は、s(1)との差分だけ計算すればO(1)で計算できる。
（変わっているのは、両端の部分だけ）

なので、s(i)は、s(i-1)からO(1)で計算できるので、
Σs(i)は全体でO(m)で計算できる。

ソースコード

double r2 = sqrt(2.0);
int m, r;
double dist(int dx){
	if(dx == 0) return 2 * r;
	if(dx == 1) return (2 + r2) * r;
	return 2 * (dx - 1 + r2) * r;
}
int main(){
	cin >> m >> r;
	double sum = 0, tsum = 0;
	
	rep(i, m) tsum += dist(i);
	rep(i, m){
		sum += tsum;
		tsum -= dist(m - 1 - i);
		tsum += dist(i + 1);
	}
	
	printf("%.9f\n", sum / m / m);
	return 0;
}