本文共 3691 字，大约阅读时间需要 12 分钟。

算法笔记4.5.2二分法拓展思考题——求多边形组成的凸边形的外接圆的最大半径

思考题如下：

给出N个线段的长度，试将它们头尾相接（顺序任意）地组合成一个凸多边形，使得该凸多边形的外接圆（即能使凸多边形的所有顶点都在圆周上的圆）的半径最大，求该最大半径。其中N不超过1e5，线段长度均不超过100，要求算法中不涉及坐标运算。

初版，正确版本在下面~

这个思考题其实，应该难在怎么求最大半径，而不是难在二分法，因为百度了一下竟然没找到，所以就仔细思索了一下，仅供思路参考，并没有过多的Debug…所以程序可能存在问题，但基本思想应该差不多。。。 ( ´･∀･｀)

评论的小伙伴指出了这个方法的不足。。就是只能求外接圆圆心在凸边形内的，在凸边形外的边角关系能找到，但是。。。没法确定二分法的范围，以及。。如何判定外接圆圆心在凸边形内部还是外部，希望大神能评论给以意见啊！先谢谢了

就说说这个求最大半径的算法思想吧：（下面的⭐等同于*）（因为这个编辑器会把字变成斜线所以没用= =）

首先，外接圆圆心到凸边形任一顶点距离都为外接圆的半径R，N边形的内角和为2π⭐（n-2)，对任意一条边 Li 来说，外接圆圆心到这条边的两个端点的直线与这条边围成一个等腰三角形，等腰三角形的底 αi 角就等于arccos((Li/2)/R)，那么根据等式2π⭐（n-2)=2⭐α1+2⭐α2+…+2⭐αn，就可以利用二分法求解了。

然后，要确定求解的范围，这里我是自己想了想，没有做严谨的数学证明，外接圆的半径肯定不会超过这个凸边形的周长C的，所以二分的范围在[0,C]之间。

最后，奉上外接圆圆心在凸边形内部的代码~(…•˘_˘•…)

实现的代码如下：

#include 
   
    #include 
    
     using namespace std;const double eps=1e-5;const double PI=acos(-1.0);double anglesum(double a[],int n,double R){	double temp=0;	for(int i=0;i
     
      eps)	{		mid=(left+right)/2;		if(anglesum(a,n,mid)>PI*(n-2))		{			right=mid;		}		else		{			left=mid;		}	}	return mid;}int main(){    double arc[100010];    int n;    while(~scanf("%d",&n))    {    	double sum=0;    	for(int i=0;i
     
    
   

测试了简单的三边形四边形都成功了，但其实，我也百度到，任意的多边形其实不一定有外接圆(￣▽￣") ，这就比较尴尬了，但是后来想了想，没有外接圆的那些图形的原因是边的摆放位置不对，而本题是顺序任意，那么就一定有外接圆啦，也就一定有最大半径了~，当然这只是外接圆圆心在凸边形内部的。。。

欢迎大家评论指正(๑•́ ₃ •̀๑)

2018.1.28修正版（待指正。。）

总设，凸边形的周长为C，凸边形的最大边边长为A，总边数为N，边 Li 与两条半径为R的边围成的等腰三角形的顶角为 αi

先将给出的边长按从大到小排序，然后把不能组成凸边形的情况给排除，即C-A小于A的情况，这时候无法围成凸边形。

首先需要判断凸边形的外接圆的圆心在凸边形外还是凸边形内还是凸边形上，

呃。。。怎么解释呢。。。就是先把最大边长A看作是外接圆的直径2R，利用这个R来求前 N-1 条边的顶角 αi ，那么这样求出来的α1+α2+…+α(n-1) 与 π 就有一个大小关系： 大于π，则外接圆圆心在凸边形内； 等于π，则外接圆圆心在凸边形的最大边上； 小于π，则外接圆圆心在凸边形外。 要说怎么严格的证明，不知道。。。但是画画图就能理解了，，你可以试一下0.0

这样就有两套方案，分别适用于外接圆圆心在凸边形内和最大边上（在最大边上也可以归于另一种，这两个它都可以使用）

第一种情况 当外接圆圆心在凸边形内或者在凸边形边上时，设外接圆半径和每条边的两个端点围起来的等腰三角形的顶角为 αi ，则2π= α1+α2+…+αn，αi=arccos((2R²-Li²)/2R²)； 第二种情况 当外接圆圆心在凸边形外时，设最长的边为A，其他的边为 Li ，设外接圆半径和每条边的两个端点围起来的等腰三角形的顶角为 αi ，那么 αA=α1+α2+…+α(n-1)，而αi=arccos((2R²-Li²)/2R²)。 关于你说的这个 αA和α1+α2+…+α(n-1) 都是增长的无法比较的问题，实际上。。。它俩虽然都增长，但是增长幅度并不同，这个，画图才能看出来。。。0.0 结论就是 如果 二分的mid如果大于真实半径R，那么αA小于α1+α2+…+α(n-1) 如果 二分的mid如果小于真实半径R，那么αA大于α1+α2+…+α(n-1) 利用这个就可以二分了

还有就是求二分的边界值问题

当外接圆圆心在凸边形内或者在凸边形边上时，这个上面已经讨论过了，它最大也不能超过周长C

当外接圆圆心在凸边形外时，这里还要进行一次二分。。

利用正弦公式和弧长公式。。。 设弧长为L，最长边还是A，半径为R 那么 α=L/R (1) A/sin(α/2)=2R (2)

虽然，R的最大值不好找，但是。。α有限制呐，所以就利用α突破，

将R=L/α带入(2)式，整理可得

Aα=2Lsin(α/2) 那么就可设 f(α)=Aα-2L*sin(α/2) 利用α属于0到2π，就可以愉快的进行二分啦 最终得到α，然后利用(1)式就得到了R 你肯定会有疑问，L不知道啊，这里我用的是C-A近似于L，易知C-A显然小于L，那么得出来的R就比用 L 代入的还要大，所以肯定大于最大的范围，所以就得到了二分的范围。。。 这里默认了下限直接用0，而评论区的大佬说，可以利用 arccosx 函数的定义域为［-1，1］，限制Li/(2R)的范围，求出R的下限，即max(Li)/2，其中i=1…n。（时间久远，我忘得差不多了，大家可以试着改一下~） 然后利用上面的核心公式就可以二分了。。

下面是我实现的代码。。。

#include 
   
    #include 
    
     #include 
     
      using namespace std;const double eps=1e-5;const double PI=acos(-1.0);double anglesum(double a[],int n,double R){    double temp=0;    for(int i=0;i
      
       eps)    {        mid=(left+right)/2;        if(anglesum(a,n,mid)
       
        eps)	{		mid=(left+right)/2;		if(f(N,a,mid)>0)		{			right=mid;		}		else		{			left=mid;		}	}	return N/mid;}double solve1(double N,double a[],int n){    double left=0,right=MaxR(N-a[n-1],a[n-1]),mid;    while(right-left>eps)    {        mid=(left+right)/2;        if(anglesum(a,n-1,mid)>anglesum1(a[n-1],mid))        {            right=mid;        }        else        {            left=mid;        }    }    return mid;}int main(){    double arc[100010];    int n;    while(~scanf("%d",&n))    {        double sum=0;        for(int i=0;i
        
         arc[n-1]) { if(anglesum(arc,n-1,arc[n-1]/2.0)>=PI) { printf("%.4f\n",solve(sum,arc,n)); } else { printf("%.4f\n",solve1(sum,arc,n)); } } else { printf("invalid data!\n"); } } return 0;}
        
       
      
     
    
   

各位大佬…评论区见~(:з」∠)

转载地址：https://meteorrain.blog.csdn.net/article/details/79079862 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！