Croc Champ 2013 - Round 2 : D. Ksusha and Square

これは落ち着いてやったら自力で解けた。
http://codeforces.com/contest/293/problem/D

問題

２次元座標上で、凸図形を構成するN個の頂点群が与えられる。
この凸図形の中にある任意の２点を選んだ時、その２点を対角線とする正方形の面積の期待値を求めよ。

解法

正方形の面積＝２点間の距離の２乗の半分、なので、全部の２点間の距離の２乗の総和を求めればよい。
この際三平方の定理より、２点の距離の２乗和＝(２点のX座標の差の２乗和)＋(２点のY座標の差の２乗和)なので、X座標とY座標それぞれに差の２乗和を取って足せばよい。

以下X座標の差の２乗和を考える。
まず凸図形内において、各X座標に相当する格子点の数P[x]を列挙していく。
この処理はO(N+maxX)程度で終えることができる。

あとは距離の２乗和については、下記の容量で累積和を使ってO(maxX)で求めることができる。
Codeforces #231 Div2. E. Lightbulb for Minister - kmjp's blog

X座標がxにあるP[x]個の点と、z＜xにある各頂点との二乗和は
$P[x] \times \sum_{z\lt x} ( P[z]*(x-z)^2 ) = P[x] \times ( (\sum P[z])*x^2 - 2* x*(\sum z*P[z]) + (\sum z^2*P[z]) )$
となるので、 $\sum z*P[z]$ と $\sum z^2*P[z]$ を管理しておけばよい。

あとは同じ処理をY座標に関して行う。

int N,X[100006],Y[100006];
vector< vector<pair<int,int> > > H;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	H.resize(2000005);
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i], X[i]+=1000000, Y[i]+=1000000;
	
	
	double ret=0;
	double T;
	FOR(k,2) {
		T=0;
		FOR(x,2000001) H[x].clear();
		FOR(i,N) {
			H[X[i]].push_back(make_pair(Y[i],Y[i]));
			if(X[i]!=X[(i+1)%N]) {
				int dx=(X[i]<X[(i+1)%N])?1:-1;
				for(x=X[i]+dx;x!=X[(i+1)%N];x+=dx) {
					ll dy=1LL*(x-X[i])*(Y[(i+1)%N]-Y[i]);
					ll y2=Y[i]+dy/(X[(i+1)%N]-X[i]);
					if((dy>=0) ^ (X[(i+1)%N]<X[i]))
						H[x].push_back(make_pair(y2,y2+((dy%(X[(i+1)%N]-X[i])!=0))));
					else
						H[x].push_back(make_pair(y2-(dy%(X[(i+1)%N]-X[i])!=0),y2));
				}
			}
		}
		
		double S1=0,S2=0;
		FOR(x,2000001) if(H[x].size()) {
			int mf=H[x][0].first,ms=H[x][0].second;
			FOR(i,H[x].size()) mf=max(mf,H[x][i].first),ms=min(ms,H[x][i].second);
			int h=mf-ms+1;
			if(h<=0) continue;
			ret += h*(T*x*x-2LL*x*S1+S2);
			T+=h;
			S1+=1LL*h*x;
			S2+=1LL*h*x*x;
		}
		FOR(i,N) swap(X[i],Y[i]);
	}
	_P("%.12lf\n",ret/(T-1.0)/T);
	
}

まとめ

過去のCodeforcesの知識が活きて良かった。