【题解】P6711 【Polygon】

Terrible · 2023-07-25 12:14:35 · 题解

注：凸包就是凸多边形。

构造思路

找一个圆，在圆上逆时针取 n 个点，使得相邻两个点距离等于给定边长，输出这 n 个点坐标。

理论论述

不想吃烤 mian() 包夹绿鸟可以不买，不想看证明可以跳过喵。 知乎上相关问题推荐

定义 \quad 如果一个多边形没有任何一个内角是优角（介于 180^\circ 到 360^\circ 的角），那么这个多边形是凸多边形。

定义' \quad 一个多边形的每条边所在直线将平面划成两部分，如果多边形其它边均在其一侧，那么这个多边形是凸多边形。

引理 1 \quad 圆上找 n 个点（n\geqslant 3）按逆时针序顺次相连 n 次得到的图形是凸 n 边形。

[证明 1]：圆上找任意三点从其一点开始按逆时针顺序连线两次后得到的夹角都严格小于 180^\circ，圆上找 n 个点顺次相连 n 次得到 n 边形，它的 n 个内角都严格小于 180^\circ，都不为平角或优角，故得到凸 n 边形。

[证明 2]：圆上任意一个弦将圆分成两部分，n 次相连得到的 n 边形的边都是圆的弦，由于按照逆时针序顺次相连，所有顶点均在每个边上或其一侧，否则顶点相连顺序不满足逆时针序，进而可知对于每一条边其它边均在其一侧，因而得到的图形是凸 n 边形。

引理 2 \quad 给定一个多边形，能够通过不改变这个多边形边长的形变使得其顶点共圆。

[证明 1]：归纳法：

1. 任意三角形都存在外接圆，证明链接；

2. 假设 n 边形的情况成立（n\geqslant 3），取定任意一个 n 边形 P，能够找到通过上述形变后顶点共圆的 n 边形 P'，取定 P' 上任一顶点记为 A，使 P' 在 A 处裂开，裂开后分别记裂口处两单侧端点为 A_1,A_2，将剩下的 n-1 个顶点和 A_1,A_2 两点固定到 P' 对应的圆上，并扩张对应的圆，裂口两侧距离 |A_1A_2| 随着 R 的增加而连续增大，且易知 0<|A_1A_2|<\boxed{\small{n\text{条边长总和}}}，如果将 |A_1A_2| 视作一条新的边，则它和其他 n 条边一起构成一个顶点共圆的 n+1 边形 P''，再由 P 的任意性和 |A_1A_2| 长度的任意性，可得构造出的 P'' 包含了 n+1 边形的所有情况。

由数学归纳定理，对于任意多边形，都可以使其通过不改变边长的形变使得其顶点共圆。

[证明 2]：下面的具体构造方法中定理部分。

具体构造方法

首先无解的条件是这些边连一个多边形都构造不出来，最长的边比其他边加起来还长，总有一段接不上，或者它们至多构成一来一回的两端。即 max>=sum-max。

除此之外，其他情况就都存在解啦。因为能组成多边形就能贴到圆上，能贴到圆上的就是凸多边形。

那么我们的当务之急是找到这个圆，不妨把圆心放到坐标系圆点，求半径 R 即可。我们可以先试试随便给一个 R_0，看看这个 R_0 是不是我们要的，它是大了还是小了，进而二分答案来确定。

考虑各个镶嵌到圆上的多边形顶点可以用一个角度 \alpha_i 来表示，因为确定了 R 和 \alpha_i 就确定了对应顶点位置 (R\cos\alpha_i,R\sin\alpha_i),i=1,2,\cdots,n，同时也方便逆时针输出点坐标。

考虑如何得到 \alpha_i：我们现在知道边长，因而至多知道两个相邻角之差，这个相邻角的差怎么求呢？

从上图可以得出半弦—半角转化公式：R\sin\dfrac{\alpha}{2}=\dfrac{a}{2}，容易反解出 \alpha=2\arcsin\left(\dfrac{a}{2R}\right)，但是有一个前提，就是弦的圆心角小于等于 180^\circ——因为 \arcsin 只能解出来锐角或直角（\leqslant 90^\circ），这意味着我们需要分情况讨论。好在这里至多会出现一个平角或优角，聪明的你应该明白为什么至多只有一个吧！

前两种情况可以统一处理，后一种情况需分开。

定理 \quad 设给定多边形边长依次为 a_1,a_2,\cdots,a_n，且 a_{max}=\max\limits_{i=1}^n(a_i)，能构成前两种情况的充要条件是 \sum\limits_{i=1}^n2\arcsin\left(\dfrac{a_i}{a_{max}}\right)\geqslant 2\pi，否则必然能构成第三种情况。

[直观理解]：

情况 2：直接意味着找到了 R。

情况 1：如果 R 大了，就合不住口了；如果 R 小了，就有交叉点了。

情况 3：如果 R 小了，反而合不住口；如果 R 大了，就有交叉点了。

[证明]：

充分性：

1. 当等号成立时，构成第二种情况。即以最长边为直径，各边对应的圆心角加和为 2\pi，正好绕圆一圈；
2. 当小于号成立时构成第一种情况。设 f(R)=\sum\limits_{i=1}^n2\arcsin\left(\dfrac{a_i}{2R}\right),R\in\left[\dfrac{a_{max}}{2},+\infty\right)，则 R 取最小值时有 f\left(\dfrac{a_{max}}{2}\right)>2\pi，易知诸 \arcsin\left(\dfrac{a_i}{2R}\right) 连续单调递减，因而整体连续单调递减，且 \lim\limits_{R\to+\infty}\arcsin\left(\dfrac{a_i}{2R}\right)=0，取 R_0 使得诸 2\arcsin\left(\dfrac{a_i}{2R_0}\right)<\dfrac{2\pi}{n}，从而 f(R_0)<2\pi，根据中值定理，必然存在一点 R_\xi\in\left[\dfrac{a_{max}}{2},R_0\right]，使得 f(R_\xi)=2\pi，从而各边绕圆整整一圈；

必要性：

3. 如果上述 f\left(\dfrac{a_{max}}{2}\right)<2\pi，根据单调递减性，不存在 R_\xi 使得 f(R_\xi)=2\pi，不能绕圆一整圈；

下证 \sum\limits_{i=1}^n2\arcsin\left(\dfrac{a_i}{a_{max}}\right)<2\pi 时必然能构成第三种情况：

4. 设 g(R)=f(R)-2\arcsin\left(\dfrac{a_{max}}{2R}\right)+2\pi-2\arcsin\left(\dfrac{a_{max}}{2R}\right)，即

根据 h(R)=\dfrac{h_1(R)}{h_2(R)},g'(R)=-\dfrac{2}{R}\left[h_1(R)-h_2(R)\right] 可知，

给定示性函数 I(R)=[g(R)<2\pi]，如果表达式为真，其值是 1；如果表达式为假，其值是 0。I(R) 前半段是 1，后半段是 0，断点是 R_\xi，可以二分求解。

构造流程：

1. 判断是否能构成多边形，若 max>=sum-max 则输出 NO SOLUTION 并结束程序；

2. 不妨令 a_n=a_{max}（题目没有要求边长的顺序，可以直接排序或将最长边交换到最后。即便要求了边长的顺序，也可对边长序列进行一次轮换，将最长边调到最后）。

3. 判断构成的多边形是否通过圆心。若 \sum\limits_{i=1}^n2\arcsin\left(\dfrac{a_i}{a_n}\right)\geqslant2\pi，二分枚举单调递减函数

找到 f(R_\xi)=2\pi 的解；

否则二分枚举单调不增示性函数 I(R)=[g(R)<2\pi] 找到断点 R=R_\xi。其中

4. 令 \alpha_i=\sum\limits_{j=1}^i2\arcsin\left(\dfrac{a_i}{2R}\right),i=1,2,\cdots,n，若 \sum\limits_{i=1}^n2\arcsin\left(\dfrac{a_i}{a_n}\right)<2\pi，则覆盖定义 \alpha_n=\alpha_{n-1}+2\pi-2\arcsin\left(\dfrac{a_n}{2R}\right)；

5. 输出 (R\cos\alpha_i,R\sin\alpha_i),i=1,2,\cdots,n。

代码：

#include<cmath>
#include<cstdio>
#include<algorithm>
const double pi=acos(-1);
int a[1001],n;double alpha[1001];
double f(double R)
{
    for(int i=1;i<=n;i++)alpha[i]=alpha[i-1]+2*asin(a[i]/(2*R));
    return alpha[n];
}
int main()
{
    int sum=0;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),sum+=a[i];
    std::sort(a+1,a+1+n);//题目对边长出现的顺序无要求
    //可以只将最大边放到最后，std::swap(a[n],*std::max_element(a+1,a+1+n));
    if(a[n]>=sum-a[n])return puts("NO SOLUTION"),0;//无解
    double l=a[n]/2.0,r=1e7,R;//半径至少等于半倍最长边，注意是 2.0
    if(f(a[n]/2.0)>=2*pi)//以最长边为直径是否能绕圆至少一圈
        while((r-l)/r>1e-10)
        {
            R=(l+r)/2;
            if(f(R)>2*pi)l=R;else r=R;
        }
    else
        while((r-l)/r>1e-10)
        {
            R=(l+r)/2;//多边形不过圆心，将最长边对应的圆周角换成对应优角
            f(R),alpha[n]=alpha[n-1]+2*pi-2*asin(a[n]/(2*R));
            if(alpha[n]<2*pi)l=R;else r=R;
        }
    for(int i=1;i<=n;i++)//有一个边的误差很大，取决于 R 的精度
        printf("%.10lf %.10lf\n",R*cos(alpha[i]),R*sin(alpha[i]));
    return 0;
}