这是一道来自《算法笔记》的题目
给定 N 个线段的长度，试将它们头尾相接（顺序任意）地组合成一个凸多边形，使得凸多边形的外接圆的半径最大，求该最大半径。其中 N 不超过 105 ，线段长度均不超过 100 ，要求算法中不涉及坐标的计算。
二分算法的本质就是通过不断迭代使left 和 right 在固定条件下逐渐靠近真实值，符合一定误差，所以实际上把该题放在二分扩展里面，这个所谓的最大半径的“最大”是不在求解中的，最大应该算题干，先组成一个有外接圆的凸多边形，然后求其半径即可。不要误入歧途在“最大”上绞尽脑汁。
sum为绿色之和
因此可以对半径长度二分，寻找圆心角之和为2∗π2*\pi2∗π的那个值即可。
2. 如果圆心在凸多边形的外部，假设最大半径是rmax,那么最长的线段的圆心角，一定等于其他线段的圆心角之和。取计算目标为其他圆心角和+2π−最大圆心角，此时情况取反。
#include<cstdio> #include<cmath> const double PI=acos(-1.0); const double eps=1e-5;//比较精度 //求圆心角之和 double totalCornerAngles(double edges[],int n,double r){ double sum = 0.0; for(int i =0;i<n;i++) sum+=asin(edges[i]/2/r)*2; return sum; } int main(){ int N;//边数 scanf("%d",&N);//输入边数 double edges[100];//边长数组 double sum;//圆心角之和 double maxAngle=0.0;//最长边对应的圆心角 double maxEdge=0.0;//最长边 //初始化edges for(int i=0;i<N;i++){ scanf("%lf",&edges[i]); if(edges[i]>maxEdge) maxEdge = edges[i];//保存最大边 } //以最长边为直径求圆心角之和，若为2π则直接返回 sum = totalCornerAngles(edges,N,maxEdge/2); if(fabs(sum-PI*2)<eps){ printf("外接圆的最大半径是最大边的一半：%.2f",maxEdge/2); return 0 ; } //半径大于最大边的一半（即斜边大于直角边） double left =maxEdge/2,right=10000000,mid; double other=0; //在误差范围内循环求解 while(right -left >eps){ mid = (right + left) /2; maxAngle=asin(maxEdge/2/mid)*2;//求出最大边对应的圆心角 sum = totalCornerAngles(edges,N,mid); other=sum-maxAngle; //如果除去最大圆心角的其他圆心角之和小于π，说明圆心在多边形外面 if(other<PI){ sum=other+2*PI-maxAngle; if( sum<2*PI) left = mid; else right = mid; } //圆心在多边形里面 else{ if(sum>2*PI) left = mid; else right = mid; } } printf("外接圆的最大半径是：%.2lf",mid); return 0; }
参考：https://blog.csdn.net/liuerin/article/details/98961797
原文：https://www.cnblogs.com/transmigration-zhou/p/12275464.html