yukicoder : No.1385 Simple Geometry 2

これは典型かな…。
https://yukicoder.me/problems/no/1385

問題

単位円上にあるN個の点の位置が指定される。
ここから3点を選んで三角形ABCを作ったときの面積の期待値を求めよ。

解法

全パターンの面積の総和を求めて、パターン数で割ろう。
2点A,Bについて、三角形OABが解に計上されるケースを考え、その総和を取ろう。
弧AB上に他の点が何個あるかによって、OABが何回分計上されるかが変化する。
累積和を取りながらX座標やY座標の総和を計算していこう。

int N;
ll L;
ll T[505050];
double S[505050];
double C[505050];
double SS;
double SC;
double DS;
double DC;


void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	
	cin>>N>>L;
	FOR(i,N) {
		cin>>T[i];
		S[i]=sin(2*pi*T[i]/L);
		C[i]=cos(2*pi*T[i]/L);
		SS+=S[i];
		SC+=C[i];
		if(i>=2) {
			DS+=S[i]*(i-1);
			DC+=C[i]*(i-1);
		}
	}
	double ret=0;
	FOR(i,N) {
		ret+=S[i]*DC-C[i]*DS;
		DS-=SS;
		DC-=SC;
		DS+=S[i]*(N-1)+S[i+1];
		DC+=C[i]*(N-1)+C[i+1];
	}
	ret /= 2;
	ret /= 1LL*N*(N-1)*(N-2)/6;
	_P("%.12lf\n",ret);
}

まとめ

シンプルな問題設定だね。