【NOI2018模拟3.27】Yja

Description

在平面上找 n 個點, 要求這 n 個點離原點的距離分别為 r 1 ,r 2 ,…,r n . 最大化這 n 個點構成的凸包面積, 凸包上的點的順序任意.不要求點全部在凸包上

n<=8

Solution

玄學幾何題其實并不是

枚舉點是否出現和一個順序，問題變成求

max(12∑i=1nr[i]∗r[imodn+1]∗sin(θi))

限制是：

∑i=1nθi=2π

然後有一個叫拉格朗日乘數的東西，可以做這個式子的極值。

設一個拉格朗日乘數 λ ，極值函數為f(x1,x2..xn),限制函數為g(x1,x2..xn)=c

那麼将目标函數改造為F(x1,x2…xn, λ )=f(x1,x2..xn)+ λ (g(x1,x2…xn)-c)

然後對該函數做偏導，每一個變量xi處的偏導為0

這樣就可以得到n個方程，足以解出n個變量。

回到這道題，我們可以發現最後偏導出來的結果形如 r[i]∗r[imodn+1]∗cos(θi)+λ=0

對于每一項都成立，并且我們知道 θi 在 [0,π] 範圍内是遞減的，于是我們可以二分這個 λ ，然後把所有的 θ 求出來。

但是注意有一個細節，你求出來的某個 θ 可能趨于0，這個時候需要舍去這種情況

别問我我也不知道為什麼

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef double db;

const db pi=acos(-);
const db eps=;

int n,lim,r[],R[];
bool vis[];
db theta[],ans;

bool check(db x) {
    fo(i,,lim) theta[i]=acos(x*/R[i]/R[i%lim+]);
    db all=;fo(i,,lim) all+=theta[i];
    return all>*pi;
}

void dfs(int x) {
    if (x>lim) {
        int mn=;
        fo(i,,lim) mn=min(mn,R[i]*R[i%lim+]);
        db le=-mn,ri=mn;
        while (ri-le>eps) {
            db mid=(le+ri)*;
            if (check(mid)) le=mid;
            else ri=mid;
        }
        fo(i,,lim) if (theta[i]<eps) return;
        db res=;
        fo(i,,lim) res+=R[i]*R[i%lim+]*sin(theta[i]);
        ans=max(ans,res/);
        return;
    }
    fo(i,,n)
        if (!vis[i]) {
            R[x]=r[i];vis[i]=;
            dfs(x+);
            R[x]=;vis[i]=;
        }
}

int main() {
    freopen("yja.in","r",stdin);
    freopen("yja.out","w",stdout);
    scanf("%d",&n);
    fo(i,,n) scanf("%d",&r[i]);
    fo(i,,n) {
        lim=i;
        dfs();
    }
    printf("%.8lf\n",ans);
    return ;
}