Circle Union

题面

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

image.png

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

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

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

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

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

image.png

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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();
}

文章作者: yijan
文章链接: https://yijan.co/2020/11/21/circle-union/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog