题目描述

　　在平面上找 \(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\)

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

\[ \begin{cases} r_1r_2\cos\theta_1=r_2r_3\cos\theta_2=\cdots=r_nr_{n+1}\cos\theta_n&=\lambda\\ \theta_1+\theta_2+\cdots+\theta_n&=2\pi \end{cases} \]

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

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
             
               pii;typedef pair
              
                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 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<
                
                 >(j-1))&1) a[++::n]=r[j]; if(::n>=3) getans(); } printf("%.10lf\n",ans/2); return 0;}