yukicoder : No.764 浮動点

ちょっと手間取ったけど解けて良かった。
https://yukicoder.me/problems/no/764

問題

2次元座標においてP(0)～P(N+1)の(N+2)点がある。
P(0)とP(N+1)の位置は確定しており、その距離はL(0)とする。

P(i)とP(i+1)の距離は確定しており、その距離をL(i)とする。
P(1)～P(N)がそれぞれ距離の条件を満たした範囲で動くとき、各点の移動可能な範囲の面積を求めよ。

P(i)について、P(0)～P(i)における距離の条件から、P(0)とP(i)間の距離の最小値minR1最大値maxR1を求めよう。
最大値はもちろんsum(L(0)～L(i-1))である。
最小値はmax(0, 2*max(L(0)～L(i-1))-sum(L(0)～L(i-1)))である。
P(i)～P(N+1)における距離の条件から、同様にP(i)とP(N+1)間の距離の最小値minR2最大値maxR2を求めよう。

すると、包除原理の要領で、求める面積は下記の通り。

• P(0)を中心とする半径maxR1の円とP(N+1)を中心とする半径maxR2の円の共通部分
• - P(0)を中心とする半径minR1の円とP(N+1)を中心とする半径maxR2の円の共通部分
• - P(0)を中心とする半径maxR1の円とP(N+1)を中心とする半径minR2の円の共通部分
• + P(0)を中心とする半径minR1の円とP(N+1)を中心とする半径minR2の円の共通部分

int N;
int L[10101];

pair<int,int> hoge(int a,int b) {
	vector<int> V;
	int i;
	for(i=a;i<=b;i++) V.push_back(L[i]);
	sort(ALL(V));
	
	int ma=V.back();
	V.pop_back();
	int sum=0;
	FORR(v,V) sum+=v;
	
	int mi=max(ma-sum,0);
	
	return {mi,sum+ma};
	
	
}

double hoge2(double a,double b,double c) {
	double pi=atan(1)*4;
	if(b>c) swap(b,c);
	if(b+c<=a) return 0;
	if(b==0 || c==0) return 0;
	if(c>=a+b) return pi*b*b;
	
	double bt = acos((a*a+b*b-c*c)/(2*a*b));
	double ct = acos((a*a+c*c-b*b)/(2*a*c));
	
	double A=b*bt*b+c*ct*c-b*sin(bt)*b*cos(bt)-c*sin(ct)*c*cos(ct);
	
	return A;
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int sum=0;
	FOR(i,N+2) cin>>L[i];
	
	for(i=1;i<=N;i++) {
		auto a=hoge(1,i);
		auto b=hoge(i+1,N+1);
		
		double S=hoge2(L[0],a.second,b.second)+hoge2(L[0],a.first,b.first)-hoge2(L[0],a.second,b.first)-hoge2(L[0],a.first,b.second);
		_P("%.12lf\n",S);
		
	}
}

まとめ

まだ辞書を作ってないので、包除原理の変換は面倒です。