HNOI模拟4.7 yist

题目大意

你需要找到 N 个点，每个点离原点的距离分别为 R1,R2,⋯,Rn ，问 N 个点形成的凸包的最大面积是多少？

数据范围

N≤8

题解

我们可以先枚举最终凸包上是哪些点，以及这些点的顺序，那么现在的问题相当于要确定一些角度 θi ，表示极角序相邻两个点的极角差，满足 ∑ni=1θi=2∗π,θi≥0 ，使得 ∑ni=1Ri∗Rimodn+1∗sin(θi) 最大。
题解说是什么通过调整可得在最优解下会有
R1R2sin(θ1)=R2R3sin(θ2)=⋯=RNR1sin(θN) ，不太懂怎么调整，反正我是暴力搞的。

前置知识

sin′(x)=cos(x),cos′(x)=−sin(x),sin(2∗π−θ)=−sin(θ)

暴力推导

我们现在相当于要最大化
∑ni=1Ri∗Rimodn+1∗sin(θi)
因为有 θ1+θ2+⋯+θn=2∗π ，那么有 θn=2∗π−θ1+θ2+⋯+θn−1
不妨令 θi 为主元， i 为任意 1 到 n−1 的整数，那么对这个函数求导，则有
Ri∗Ri+1∗cos(θi)−Rn∗R1∗cos(θ1+θ2+⋯+θn−1)=0
Ri∗Ri+1∗cos(θi)=Rn∗R1∗cos(θn)
以此类推，就得到了上面那条式子了。

那么剩下的事情就非常简单了，现在相当于我们要求出一个最小的 λ=R1∗R2∗cos(θ1)=⋯=RN∗R1∗cos(θN) ，使得 θ1+θ2+⋯+θN=2∗π ，这个直接二分就可以了。

时间复杂度是 O(n!∗2n∗logAns) 。