题目描述

　　在平面上找 \(n\) 个点，要求这 \(n\) 个点离原点的距离分别是 \(r_1,r_2,\ldots,r_n\)，最大化这 \(n\) 个点构成的土包的面积。这些点的顺序任意。

　　\(n\leq 8\)

题解

　　先枚举凸包上的点和顺序。

　　不妨设 \(r_{n+1}=r_1\)

　　面积为：\(\frac{1}{2}(r_1r_2\sin \theta_1+r_2r_3\sin \theta_2 + \cdots + r_nr_{n+1}\theta_n)\)

　　那么问题就是最大化 \(r_1r_2\sin \theta_1+r_2r_3\sin \theta_2 + \cdots + r_nr_{n+1}\theta_n\)，条件是 \(\theta_1+\theta_2+\cdots \theta_n=2\pi\)

　　应用拉格朗日乘数法，有：

　　观察到 \(\theta_1,\theta_2,\ldots,\theta_n\) 关于 \(\lambda\)单调，所以可以二分 \(\lambda\) 算出 \(\theta_1,\theta_2,\ldots,\theta_n\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<cmath>

#include<functional>

#include<assert.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

void sort(int &a,int &b)

{

	if(a>b)

		swap(a,b);

}

void open(const char *s)

{

#ifndef ONLINE_JUDGE

	char str[100];

	sprintf(str,"%s.in",s);

	freopen(str,"r",stdin);

	sprintf(str,"%s.out",s);

	freopen(str,"w",stdout);

#endif

}

int rd()

{

	int s=0,c;

	while((c=getchar())<'0'||c>'9');

	do

	{

		s=s*10+c-'0';

	}

	while((c=getchar())>='0'&&c<='9');

	return s;

}

void put(int x)

{

	if(!x)

	{

		putchar('0');

		return;

	}

	static int c[20];

	int t=0;

	while(x)

	{

		c[++t]=x%10;

		x/=10;

	}

	while(t)

		putchar(c[t--]+'0');

}

int upmin(int &a,int b)

{

	if(b<a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int upmax(int &a,int b)

{

	if(b>a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int n;

const double eps=1e-9;

const double pi=acos(-1);

int a[10];

double ans=0;

auto gao=[](double x){return x<0?x+2*pi:x;};

auto calc=[](double x){double s=0;for(int i=1;i<=n;i++)s+=gao(acos(x/a[i]/a[i+1]));return s;};

void getans()

{

	sort(a+1,a+n+1);

	a[n+1]=a[1];

	do

	{

		double s=0;

		double l=0,r=1e6;

		for(int i=1;i<=n;i++)

			r=min(r,(double)a[i]*a[i+1]);

		l=-r;

		if(calc(l)<2*pi||calc(r)>2*pi)

			continue;

		while(r-l>1e-5)

		{

			double mid=(l+r)/2;

			if(calc(mid)<2*pi)

				r=mid;

			else

				l=mid;

		}

		for(int i=1;i<=n;i++)

			s+=a[i]*a[i+1]*sin(acos(l/a[i]/a[i+1]));

		ans=max(ans,s);

	}

	while(next_permutation(a+2,a+n+1));

}

int r[10];

int main()

{

	open("b");

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%d",&r[i]);

	if(n<=2)

	{

		printf("0\n");

		return 0;

	}

	for(int i=1;i<1<<n;i++)

	{

		::n=0;

		for(int j=1;j<=n;j++)

			if((i>>(j-1))&1)

				a[++::n]=r[j];

		if(::n>=3)

			getans();

	}

	printf("%.10lf\n",ans/2);

	return 0;

}