99.9%的人不会做的结论题

学C++的第N天

2024-12-21 20:56:55

发布于：上海

45阅读

0回复

0点赞

见：https://www.acgo.cn/problemset/info/33690
题解

引理一必存在一圆外接于一个边长固定的多边形
显然

引理二正四边形的面积最大值当且仅当其内接于一个圆时取到
考虑多边形 $A_1A_2A_3A_4$ , 其边长为 $a_1,a_2,a_3,a_4$ , 对 $\triangle A_1A_2A_4$ 和 $\triangle A_3A_2A_4$ 分别使用余弦定理，可得：

$\begin{cases} |A_2A_4|^2=a_1^2+a_4^2-2a_2a_4\cos A_1\\ |A_2A_4|^2=a_2^2+a_3^2-2a_2a_3\cos A_2\\ \end{cases}\tag{1}$

又由正弦定理，可得 $S=\cfrac{1}{2}\left(a_1a_4\sin A_1+a_2a_3\sin A_3\right)$ ，从而：

$\begin{cases} a_1a_4\cos A_1-a_2a_3\cos A_3=\cfrac{1}{2}\left(a_1^2+a_4^2-a_2^2-a_3^2\right)\\ a_1a_4\cos A_1+a_2a_3\cos A_3=2S \end{cases} \tag{2}$

整理即得：

$S=\sqrt{(p-a_1)(p-a_2)(p-a_3)(p-a_4)-a_1a_2a_3a_4\cos^2\cfrac{A_1+A_3}{2}}，p=\cfrac{1}{2}\sum_i a_i\tag{3}$

显然， $a_1,a_2,a_3,a_4$ 确定时，若要 $S$ 最大，则必有 $\cos^2\cfrac{A_1+A_3}{2}=0$ ，即 $A_1+A_3=\pi$ ，所以 $A_1A_2A_3A_4$ 四点共圆。
引理三圆内接多边形的面积大小与其各边排列无关
考虑圆内接多边形 $A_1A_2A_3...A_n$ 和其外接圆 $\odot O$ , 记其半径为 $r$ , 各边边长为 $a_1,a_2......a_n$ , 过 $O$ 作 $OB_1\bot A_1A_2,OB_2\bot A_2A_3...OB_n\bot A_nA_1$ , 根据垂径定理， $OB_1,OB_2...OB_n$ 都是半径且分别平分 $A_1A_2,A_2A_3...A_nA_1$ ，因此：

$\begin{align} S&=\sum S_{\triangle A_iOA_{i+1}}\\ &=\sum \cfrac{1}{2}a_i\sqrt{r^2-\cfrac{1}{4}a_i^2} \end{align}\tag{4}$

所以内接于同一个圆的，各边边长组成的有序 $n$ 元组等价的多边形面积相等。接下来证明 $A_1A_2A_3...A_n$ 排列各边必内接于 $\odot O$ , 令多边形 $A_1A_2A_3...A_n$ 的圆心角分别为 $\theta_1,\theta_2...\theta_n$ 现将多边形各边重新排列，其各边所对圆心角变为 $\theta’_1,\theta'_2...\theta'_n$ , 由于 $\theta_1,\theta_2...\theta_n$ 本质上是 $\theta’_1,\theta'_2...\theta'_n$ 的一个排列，因此：

$\sum_i \theta_i=\sum_i \theta'_i=2\pi\tag{5}$

同时易得变换后的多边形 $A'_1A'_2A'_3...A'_n$ 的各点依旧在 $\odot O$ 上，因此多边形 $A'_1A'_2A'_3...A'_n$ 依旧内接 $\odot O$ .
引理四边长固定的多边形在其内接于一圆时面积取得最大值
充分性：
考虑多边形 $A_1A_2A_3...A_n$ 的相邻四个顶点 $A_{i}A_{i+1}A_{i+2}A_{i+3}$ (规定 $i$ 为正整数且 $A_{i+n}$ 等价于 $A_i$ )。若 $A_{i}A_{i+1}A_{i+2}A_{i+3}$ 不共圆，则必定可以找到一个四边形 $A'_{i}A'_{i+1}A'_{i+2}A'_{i+3}$ 使得其各个边的边长和四边形 $A_{i}A_{i+1}A_{i+2}A_{i+3}$ 的相等，根据引理二，有 $S_{A'_{i}A'_{i+1}A'_{i+2}A'_{i+3}}>S_{A_{i}A_{i+1}A_{i+2}A_{i+3}}$ 。同时若将四边形 $A_{i}A_{i+1}A_{i+2}A_{i+3}$ 替换为四边形 $A'_{i}A'_{i+1}A'_{i+2}A'_{i+3}$ 。可使多边形 $A_1A_2A_3...A_n$ 剩余部分形状不变。因此要使 $A_1A_2A_3...A_n$ 的面积最大，其任意相邻的四个顶点共圆，因此 $A_1A_2A_3...A_n$ 内接于一圆。
必要性：
若内接于圆的多边形 $A_1A_2A_3...A_n$ 面积并未达到最大，则考虑将 $A_1A_2,A_2A_3......A_nA_1$ 以及 $\widehat{A_1A_2},\widehat{A_2A_3}......\widehat{A_nA_1}$ 进行形变，使得(单个边或弓形的形状不变)使得其其面积更大，此时：

$S_{新多边形}+S_{各弓形}>S_{旧多边形}+S_{各弓形}=S_{圆}\tag{6}$

然而整个图形的边长并未改变，面积却增加了，与等周定理矛盾，因此内接于圆的多边形 $A_1A_2A_3...A_n$ 面积必定达到最大。同理，面积最大的 $A_1A_2A_3...A_n$ 唯一。
解答
根据引理四，所求多边形 $A_1A_2A_3...A_n$ 必内接于一圆，记其各边边长为 $a_1,a_2...a_n$ ，外接圆半径为 $r$ ，各边所对应圆心角为 $\theta_1,\theta_2...\theta_n$ 。注意到：

$\cfrac{1}{2}\theta_i=\arcsin \cfrac{a_i}{2r}\Leftrightarrow\sum\arcsin \cfrac{a_i}{2r}=\cfrac{1}{2}\sum\theta_i=\pi\tag{7}$

再由欧拉公式变形：

$\begin{align} &\arcsin \cfrac{a_i}{2r}=-\sqrt{-1}\ln\left(\sqrt{-1}\cdot\cfrac{a_i}{2r}+\sqrt{1-\left(\cfrac{a_i}{2r}\right)^2}\right)\Leftrightarrow \\ &\sum\ln\left(\sqrt{-1}\cdot \cfrac{a_i}{2r}+\sqrt{1-\left(\cfrac{a_i}{2r}\right)^2}\right)=\sqrt{-1}\cdot\pi \tag{8} \end{align}$

$(8)$ 的等式两边同取指数，得：

$\prod\left(\sqrt{-1}\cdot \cfrac{a_i}{2r}+\sqrt{1-\left(\cfrac{a_i}{2r}\right)^2}\right)=e^{\sqrt{-1}\pi}=-1\tag{9}$

因此可得 $r$ 满足方程：

$\prod\left(\sqrt{-1}\cdot \cfrac{a_i}{2r}+\sqrt{1-\left(\cfrac{a_i}{2r}\right)^2}\right)+1=0\tag{10}$

求出 $r$ 的解析解后，根据引理三可得 $S$ 的值。
展示结果的代码(注意直接提交该代码不能通过该题，因为开了O2，请使用Dev编译运行)

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

const int prec0 = 500000;//表示精度，值越大，精度越高，运行时间越长。
const double inf = 100000000;
int a[10];
double r1 = 0;
int maxnum = -1, sum = 0, n = 0;

struct complex_number{
    double real_part;
    double imaginary_part;
}result;

double get_root(double x, int prec){//C++开大整数根号的精度堪忧，此处写牛顿迭代开根号备用，prec表示精度
    if(x <= 1) return sqrt(x);
    int r = x;
    vector <double> table;
    table.push_back(1);
    for(int i = 1; i <= prec; i++){
        table.push_back((1.0 / 2.0) * (table[i - 1] + r / table[i - 1]));
    }
    return table[prec];
}

double quick_pow(double x, int power){//快速幂算法
    double result = 1;
    while(power){
        if(power & 1)
            result = result * x;
        x = x * x;
        power >>= 1;
    }
    return result;
}

double find_value(double x){//计算r = x时(10)式等式左侧减去1的值的实部
    result.imaginary_part = 0;
    result.real_part = 0;
    if(2 * x < maxnum * 1.0) return 0 - inf;
    complex_number num;
    for(int i = 1; i <= n; i++){
        if(i == 1){
            result.imaginary_part = (a[i] * 1.0) / (2.0 * x);
            result.real_part = sqrt(1.0 - quick_pow((a[i] * 1.0) / (2.0 * x), 2));
        }else{
            num.imaginary_part = (a[i] * 1.0) / (2.0 * x);
            num.real_part = sqrt(1.0 - quick_pow((a[i] * 1.0) / (2.0 * x), 2));
            double p0 = result.real_part * num.real_part - result.imaginary_part * num.imaginary_part;
            double q0 = result.real_part * num.imaginary_part + result.imaginary_part * num.real_part;
            result.real_part = p0;
            result.imaginary_part = q0;
        }
    }
    return result.real_part;
}

double find_radius(){
    double ans = 0;
    double mininum = inf;
    for(int i = maxnum / 2; i <= sum * prec0; i++){
        if(fabs(find_value((i * 1.0) / prec0) + 1) < mininum){
            mininum = fabs(find_value((i * 1.0) / prec0) + 1);
            ans = (i * 1.0) / prec0;
        }
    }
    return ans;
}

void print_ans(){
    double value = 0;
    for(int i = 1; i <= n; i++){
        value += a[i] * sqrt(quick_pow(r1, 2) - 0.25 * quick_pow(a[i], 2));
    }
    value /= 2;
    cout << "The maximum area is : ";
    printf("%.15f", value);
    cout << endl << "The radius of the circumcircle is : ";
    printf("%.7f", r1);
}

int main(){
    //输入为 5 2 2 2 3 3,精确答案为9.6824,r1 = 2.0656
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        maxnum = max(maxnum, a[i]);
        sum += a[i];
    }double flag = sum / 2;
    for(int i = 1; i <= n ;i++){
        if(a[i] > flag){
            cout << "doesn't exsist";
            return 0;
        }
    }
    r1 = find_radius();
    print_ans();
    return 0;
}

如果你看到一篇在其他平台上但内容大致相同的文章，不要怀疑是我抄袭，因为那篇也是我写的。

有帮助，赞一个

去预览

0/2000

全部评论 4

学C++的第N天
顶

2024-12-21 来自上海
1
复仇者_Erika (不加团队
古希腊掌管题解版书的神

2024-12-21 来自湖南
0
‮队团加不）ด้้童帅_者仇复
强强强

2024-12-21 来自广东
0
- ‮队团加不）ด้้童帅_者仇复
  回复‮队团加不）ด้้童帅_者仇复
  看不懂一点
  
  2024-12-21 来自广东
  0
- 复仇者_必胜啊（不加团队
  回复‮队团加不）ด้้童帅_者仇复
  我去逆天
  
  2024-12-24 来自广东
  0
‮队团加不）ด้้童帅_者仇复

2024-12-07 来自广东
0

全部评论 4

热门讨论