【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;
}