【算法】N个线段求最大外接圆半径

发表于 | 分类于
字数统计: 862 字 | 阅读时长 ≈ 3 分钟

N个线段求最大外接圆半径

题目

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

思路

二分算法的本质就是通过不断迭代使left 和 right 在固定条件下逐渐靠近真实值，符合一定误差，所以实际上把该题放在二分扩展里面，这个所谓的最大半径的“最大”不应该是用函数来求解，最大应该是考虑如何找到这个最大的半径。所以先组成一个有外接圆的凸多边形，然后求其半径即可。不要误入歧途在“最大”上绞尽脑汁。 外接圆圆心与每个线段顶点连接后会有一个圆心角，如果圆心在凸多边形内部，则所有圆心角之和应该为2π。如果圆心在凸多边形外部，则最大的圆心角等于其他圆心角之和。 因此设定初值，求出每个线段对应的圆心角，使所有圆心角之和等于2π。不断迭代逼近真值即可。当所求圆心角大于2π时，增大r尝试，小于2π时，缩小r尝试。 当圆心在多边形外面时，取圆心角之和为其他圆心角 + 2π - 最大圆心角，同时逼近的方向与前面相反。半径应该大于等于最大边的一半。其中等于的情况单独处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include<string>
#include<algorithm>
using namespace std;

const double eps = 1e-8;
const double pi = acos(-1.0);

#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define More(a,b) (((a)-(b))>(eps))
#define Less(a,b) (((a)-(b))>(-eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
#define LessEqu(a,b) (((a)-(b))<(eps))

double total(int length[], int N, double r)//计算圆心角之和
{
	double sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum += asin(length[i] / 2 / r) * 2;
	}
	return sum;
}

bool cmp(int a, int b)//用来比较大小
{
	return a > b;
}

double MaxR(int N, int length[])
{
	double maxLength;//记录最长边
	double maxDigree;//记录最大圆心角
	double sum;//记录圆心角之和

	sort(length, length + N, cmp);
	maxLength = length[0];
	sum = total(length, N, maxLength);

	if (Equ(sum,2*pi))//如果圆心角和2pi相等，返回最大边的一半就是外接圆的半径
	{
		return maxLength / 2;
	}

	double left = maxLength / 2;
	double right = 100000;
	double mid;
	double other = 0;//记录剩下的圆心角是多大用来判断圆心位置

	while (More(right,left))//用二分来求半径
	{
		mid = (left + right) / 2;
		maxDigree = asin(maxLength / 2 / mid) * 2;//求出最大边对应的圆心角
		sum = total(length, N, mid);
		other = sum - maxDigree;
		//如果除去最大圆心角的其他圆心角之和小于π，说明圆心在多边形外面
		if (other < pi)
		{
			sum = other + 2 * pi - maxDigree;
			if (Less(sum , 2 * pi))
				left = mid;
			else
				right = mid;
		}
		//圆心在多边形里面
		else
		{
			if (More(sum , 2 * pi))
				left = mid;
			else
				right = mid;
		}
	}
	return mid;
}

int main()
{
	int N;//记录有多少个线段
	int length[10000];//记录线段的长度
	
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> length[i];
	}
	double r = MaxR(N, length);
	cout << r;
	return 0;
}
0%