yja[jzoj5606]

发表于 分类于

题意

在平面上找 $n$ 个点, 要求这 $n$ 个点离原点的距离分别为 $r_1, r_2, \cdots, r_n$。 最大化这 $n$ 个点构成的凸包面积。凸包上的点的顺序任意。

$n\leq 8,r_i\leq 1000$

题解

拉格朗日乘数法模板题。

由于 $n$ 比较小，我们可以暴力枚举这 $n$ 个点顺时针的顺序，一共有 $(n-1)!$ 种。$n$ 个点分别和原点连线，设这 $n$ 条直线的夹角为 $\alpha i$，显然 $a_i$ 不会超过 $\pi$ 。凸包面积为 $\frac{1}{2}\sum{i=1}^nr_ir_{i% n+1}\sin\alpha_i$。

好看一点，设 $R_i=r_ir_{i % n+1}$，我们需要最大化 $\sum_{i=1}^nR_i\sin \alpha _i$，满足条件 $\sum \alpha_i=2\pi$。

由拉格朗日乘数法的套路，设函数 $F(\alpha_1,\alpha_2,\cdots,\alpha_n,\lambda)=\sum_{i=1}^nR_i\sin \alpha i+\lambda(2\pi-\sum{i=1}^n\alpha_i)$。

求偏导数可得：

$$\frac{\partial F}{\partial \alpha_i}=R_i\cos {\alpha_i}-\lambda=0 \ \frac{\partial F}{\partial \lambda}=2\pi-\sum_{i=1}^na_i=0$$

也就是：$\cos \alpha_i=\frac{\lambda}{R_i}$。

当 $0\leq \alpha_i\leq \pi$ 时，$\cos \alpha_i$ 单调递减。

满足单调性，那么我们就可以二分这个 $\lambda$，然后就可以算出此时的 $a_i$ 了。

时间复杂度 $O(n!\log Ans)$。

注意二分的范围

程序

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
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first

const db pi=acos(-1.);
db ans;
int n,l[9],pos[9],bo[9];
db R[9];
inline void solve()
{
	db mi=1e9;
	fo(i,1,n) mi=min(mi,R[i]=l[pos[i]]*l[pos[i%n+1]]);
	db l=-mi,r=mi,mid,sum=0;
	fo(tim,0,60)
	{
		mid=(l+r)/2.;
		sum=0;
		fo(i,1,n) sum+=acos(mid/R[i]);
		if(sum<pi*2) r=mid;
		else l=mid;
	}
	sum=0;
	fo(i,1,n) sum+=sin(acos(mid/R[i]))*R[i];
	ans=max(ans,sum);
}
void dfs(int k)
{
	if(k>n) return solve();
	fo(i,2,n) if(!bo[i])
	{
		bo[i]=1; pos[k]=i; dfs(k+1);
		pos[k]=0; bo[i]=0;
	}
}
int main()
{
	FO(yja);
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&l[i]);
	bo[1]=1; pos[1]=1;
	dfs(2);
	printf("%.10lf",ans/2.);
	return 0;
}