【NOI2018模拟】Yja

【NOI2018模拟】Yja

Description

　　在平面上找(n)个点，要求这 (n)个点离原点的距离分别为 (r1,r2,...,rn) 。最大化这(n) 个点构成的凸包面积，凸包上的点的顺序任意。
　　注意：不要求点全部在凸包上。

Input

　　第一行一个整数 (n)。
　　接下来一行$ n$ 个整数依次表示 (ri)。

Output

　　输出一个实数表示答案，要求绝对误差或相对误差 (≤ 10^{-6})。

Sample Input

4
5
8
58
85

Sample Output

2970

Hint

【数据范围与约定】
　　对于前 (20%) 的数据，(n ≤ 3)；
　　对于前$ 40%$ 的数据，(n ≤ 4)；
　　对于另 (20%) 的数据，(r1 = r2 = ... = rn)；
　　对于 (100%) 的数据，(1 ≤ n ≤ 8，1 ≤ ri ≤ 1000)。

前置知识：拉格朗日乘数法:

https://blog.csdn.net/the_lastest/article/details/78136692

我们可以用(sum_{i=1}^n i!)的复杂度枚举凸包的所有情况。因为肯定是选最长的(i)条线段，所以不需要(2^i)枚举集合。

题目中的几个偏导方程是：

[egin{align} heta _1+ heta_2+dots+ heta_n=0\ r_i*r_{i\%n+1}*cos( heta _i)+lambda=0\ end{align} ]

由于(cos( heta))在([-pi,pi])之间是单调递减的，所以我们可以二分(lambda)然后反解出( heta_i)并检验是否满足题意。

如果某个( heta_i)与(0)非常接近就应该舍去。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 10
#define eps 1e-9

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n;
int r[N];
bool cmp(int a,int b) {return a>b;}
int st[N];
double val[N];
double ans;

const double pi=acos(-1);

double chk(int n,double ans) {
	double tot=0;
	for(int i=1;i<=n;i++) {
		if(fabs(ans)>fabs(val[i])) {
			exit(-1);
		}
		tot+=acos(-ans/val[i]);
	}
	if(tot>2*pi+eps) return 1;
	else return 0;
}

int q[N];
double solve(int n) {
	double l,r,mid;
	double ans=0;
	while(1) {
		for(int i=1;i<=n;i++) st[i]=::r[q[i]];
		for(int i=1;i<n;i++) val[i]=st[i]*st[i+1];
		val[n]=st[n]*st[1];
		l=-1e9,r=1e9;
		for(int i=1;i<=n;i++) {
			l=max(l,-val[i]);
			r=min(r,val[i]);
		}
		while(l+1e-5<r) {
			mid=(l+r)/2.0;
			if(chk(n,mid)) r=mid-eps;
			else l=mid;
		}
		double now=0;
		double angle_tot=0;
		for(int i=1;i<=n;i++) {
			double angle=acos(-l/val[i]);
			if(angle<eps) now-=1e9;
			angle_tot+=angle;
			now+=val[i]*sin(angle);
		}
		ans=max(ans,now);
		if(!next_permutation(q+1,q+1+n)) break;
	}
	return ans;
}

int main() {
	n=Get();
	for(int i=1;i<=n;i++) r[i]=Get();
	sort(r+1,r+1+n,cmp);
	for(int i=3;i<=n;i++) {
		for(int j=1;j<=i;j++) q[j]=j;
		ans=max(ans,solve(i));
	}
	cout<<fixed<<setprecision(7)<<ans/2.0;
	return 0;
}