Good Bye 2015 : G. New Year and Cake

Editorial見て方針はすぐ理解できたけど、ACまで割と苦戦した。
http://codeforces.com/contest/611/problem/G

問題

２次元座標において、N頂点の凸多角形が与えられる。
この多角形をそのうち１個の対角線で2分割したとき、失望度を2*(大きい方の面積-小さい方の面積)とする。
この多角形にはN*(N-3)/2個の対角線があるが、各対角線で多角形を２分割した場合の失望度の和を求めよ。

解法

(大きい方の面積)-(小さい方の面積)=(全体の面積)-2*(小さい方の面積)
なので、N*(N-3)/2通りの分割において、小さい方の面積の総和を求めることを考える。

対角線の片方の端をx番の点とする。
もう片方の端が(x+1)...(N-1)となるような分割における小さい方の面積の総和を求めたい。
そこで、[x...y]番の頂点からなる多角形が多角形全体の面積の半分以下となるような最大のyを尺取法で求めよう。

すると、分割する対角線のもう片方の端点が(x+1),(x+2),...,yとなるような多角形の面積の総和は、A(a,b,c)をa,b,cの３点からなる三角形の面積で表現するとして
A(x,x+1,y)*(y-x)+A(x+1,x+2,y)*(y-x-1)+A(x+1,x+2,y)*(y-x-1)....
となる。x,yを更新しながら、上記総和を更新していこう。

同様に、もう片方の端点が(y+1)以降の場合は[(y+1)..N-1,0,...,x]の頂点で囲まれた側の多角形が減算すべき小さい方の面積となるので、こちらも同様に総和を更新していく。

ll S;
ll mo=1000000007;
ll N;
ll X[505050],Y[505050],SAY,SAX,SBX,SBY;

ll area(int a,int b,int c) {
	return ((X[c]-X[a])*(Y[b]-Y[a])-(Y[c]-Y[a])*(X[b]-X[a]));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	X[N]=X[0];
	Y[N]=Y[0];
	for(i=1;i<N-1;i++) S+=area(0,i,i+1);
	ll TS = S%mo*((N*(N-3)/2)%mo)%mo;
	
	ll A=0,TA=0;
	ll B=0,TB=0;
	FOR(x,N-3) {
		B+=area(0,N-2-x,N-1-x);
		(TB+=B%mo)%=mo;
	}
	
	SAX=X[0]+X[1];
	SAY=Y[0]+Y[1];
	for(x=2;x<N;x++) SBX+=X[x], SBY+=Y[x];
	y=1;
	FOR(x,N-1) {
		while(y+2<=N && (A+area(x,y,y+1))<=S/2) {
			A+=area(x,y,y+1);
			(TA+=A%mo)%=mo;
			(TB+=(mo-B%mo))%=mo;
			B-=area(x,y+1,y+2);
			y++;
			SAX+=X[y];
			SAY+=Y[y];
			SBX-=X[y];
			SBY-=Y[y];
		}
		(TS += 2*(2*mo-TA-TB))%=mo;
		A-=area(x,x+1,y);
		B+=area(x,x+1,y+1);
		
		SAX-=X[x];
		SAY-=Y[x];
		TA -= (SAX-(y-x)*X[x])%mo*(Y[x+1]-Y[x])%mo-(SAY-(y-x)*Y[x])%mo*(X[x+1]-X[x])%mo;
		TB += (SBX-(N-y-1)*X[x])%mo*(Y[x+1]-Y[x])%mo-(SBY-(N-y-1)*Y[x])%mo*(X[x+1]-X[x])%mo;
		TA=(mo+TA%mo)%mo;
		TB=(mo+TB%mo)%mo;
	}
	
	cout<<TS<<endl;
}

まとめ

x,yを尺取法でスライドしていく計算過程で頂点のX座標・Y座標の累積和を使ったりするので結構面倒。
Editorialも最初「尺取法で頑張る」としか書いてないし、具体的な計算過程を書いていくのはなかなかしんどいのでさぼってしまっている。
…と思ったらEditorialがいつの間にか充実してた。