Finding the maximum radius of circumscribed circle by dichotomy

Title Description

Given the length of N line segments, we try to combine their head and tail to form a convex polygon, so that the radius of the circumscribed circle of the convex polygon (each vertex of the polygon is on the circle) is the largest, and the maximum radius is calculated. Where n < = 10 ^ 5, the length of the line segment shall not exceed 100, and the calculation of coordinates shall not be involved in the algorithm.

Train of thought:

The essence of the bisection algorithm is to make left and right close to the real value gradually under fixed conditions through continuous iteration, which conforms to certain errors. Therefore, the problem is actually put in the bisection expansion. The so-called "maximum" of the maximum radius is not in the solution, and the maximum problem should be solved. First, a convex polygon with circumscribed circle is formed, and then its radius can be calculated. Don't go astray and rack your brains on "the biggest".
When the center of circumscribed circle is connected with the vertex of each line segment, there will be a center angle. If the center is inside the convex polygon, the sum of all center angles should be 2 π. If the center is outside the convex polygon, the maximum center angle is equal to the sum of the other center angles.
Therefore, set the initial value, and find out the corresponding center angle of each line segment, so that the sum of all center angles is equal to 2 π. It is enough to approach the true value repeatedly. When the center angle is greater than 2 π, increase r-try, and when it is less than 2 π, decrease r-try.
When the center of the circle is outside the polygon, the sum of the center angles is taken as the other center angles + 2 π - maximum center angles, and the direction of approximation is opposite to the front.
The radius should be greater than or equal to half of the maximum edge. The equal cases are treated separately.

The code is as follows

  #include<cstdio>
 #include<cmath>
 const double PI=acos(-1.0);
 const double eps=1e-5;//Comparative accuracy
  //Find the sum of center angles
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;
}
//Radius by dichotomy

int main()
{

    int N;//Edge number
    scanf("%d",&N);//Input edge number
    double edges[N];//Side length array

    double sum;//Sum of center angles
    double maxAngle=0.0;//Center angle of the longest edge
    double maxEdge=0.0;//Longest edge


    //Initialize edges
    for(int i=0;i<N;i++)
    {
        scanf("%lf",&edges[i]);
        if(edges[i]>maxEdge)
            maxEdge = edges[i];//Save Max edge
    }
    //Take the longest side as the diameter to find the sum of center angles, if it is 2 π, it will return directly
    sum = totalCornerAngles(edges,N,maxEdge/2);
    if(fabs(sum-PI*2)<eps)
    {
        printf("The maximum radius of the circumscribed circle is half of the maximum edge:%.2f",maxEdge/2);
        return 0 ;
    }

    //Radius greater than half of the largest edge (i.e. bevel greater than right angle edge)
    double left =maxEdge/2,right=10000000,mid;
    double other=0;

     //Cycle solution within the error range
    while(right -left >eps)
    {
         mid = (right + left) /2;
         maxAngle=asin(maxEdge/2/mid)*2;//Find the center angle corresponding to the largest edge
         sum = totalCornerAngles(edges,N,mid);
         other=sum-maxAngle;
         //If the sum of other center angles excluding the maximum center angle is less than π, the center is outside the polygon.
         if(other<PI)
         {
             sum=other+2*PI-maxAngle;
             if( sum<2*PI)
                 left = mid;
             else
                 right = mid;
         }
         //The center of the circle is in the polygon
         else
         {
             if( sum>2*PI)
                    }
    }
    printf("The maximum radius of the circumscribed circle is:%.2f",mid);
    return 0;
 }