Circle Union

题面

首先考虑,如果所有圆的交是一个面积而不是一个点,那么一定不优。因为可以通过调整,把一些圆从交往外拖的方式,让交的面积进行很多次贡献,答案肯定变优。所以边界的交一定是一个点。

image.png

如图,我们现在相当于是在给每个圆分配一个角度(例如圆 CC\ang KNO),使得角度的和是 2π2\pi 同时面积的并尽量大。

对于同一个圆来说,如果半径和角度都确定,显然当 ON,KNON,KN 相等的时候也就是对称的时候面积取到最值。这种情况下,也就是面积的上界是

S(θ)=2θr22+2r2sin(πθ)2=θr2+r2sin(θ)\begin{aligned} S(\theta) &= \frac{2\theta r^2}{2} + 2\frac{r^2 \sin(\pi - \theta)}{2}\\ &= \theta r^2 + r^2\sin(\theta)\\ \end{aligned}

我们对这个东西求个导,发现是

S(θ)=r2+r2cos(θ)S'(\theta) = r^2 + r^2\cos(\theta)

这个东西在 0<θ<π0 < \theta < \pi 的时候是单减的。

考虑两个圆,如果对于一种分配角度的方式使得它们的导数不同,那么一定这样调整:

image.png

由于我们已经固定了角度的和,加入导数大的向右调整,导数小的向左调整,那么一定可以让答案变优,因为导数单减,变化率大的移动过程中带来的变化一定更多。

所以最优秀的方案一定是所有圆的函数的导数相等。

同时,我们可以说明如果所有圆的函数导数相等,那么取到的情况一定是上面说的对称的情况。

考虑之前那个图,用余弦定理算一下对称情况下公共弦的大小:

x=2r22r2cos(πθ)=2(r2+cos(θ))x = \sqrt{2r^2 - 2r^2\cos{(\pi - \theta)}} = \sqrt{2(r^2 + \cos(\theta))}

发现这个东西就是 2S(θ)\sqrt{2S'(\theta)} ,所以导数相等的时候,安排角度后正好可以让所有弦相等,取到的是上界。

由于这个导函数有单调性,我们二分一下导数,然后看看角度和是否为 2π2\pi 即可。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const double pi = acos( -1 );
int n , m;
int R[MAXN];

bool chk( double x ) {
	double re = 0;
	rep( i , 1 , n ) if( x < 2 * R[i] * R[i] ) {
		re += acos( x / ( R[i] * R[i] ) - 1 );
	}
//	printf("%.6lf\n",re);
	return re < 2 * pi;
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",R + i);
	double l = 0 , r = 3e12;
	rep( i , 1 , 100 ) {
		double mid = ( l + r ) / 2;
		if( chk( mid ) ) r = mid;
		else l = mid;
	}
	double re = 0;
	rep( i , 1 , n ) if( l < 2 * R[i] * R[i] ) {
		double th = acos( l / ( R[i] * R[i] ) - 1 );
		re += R[i] * R[i] * ( th + sin( th ) );
	}
	printf("%.10lf",re);
}

signed main() {
//	freopen("input","r",stdin);
//	freopen("o.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}

\