关于《算法笔记》4.5.2二分法拓展中思考题之外接圆的思考

68 阅读 0 评论 45 点赞

我是靠谱客的博主高挑水蜜桃，最近开发中收集的这篇文章主要介绍关于《算法笔记》4.5.2二分法拓展中思考题之外接圆的思考，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

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

前言

该问题的主要任务是利用二分法计算出最大外接圆的半径，关于此算法的具体实现方法在网络上已经有了很多的例子，在此处不再赘述。文末附上一段用C语言编写的解答。

本文将讨论该问题中最引人注意的外接圆问题。

首先，应当明确外接圆的存在是题目已经给出的既定条件，即不需要去考虑怎样求得该外接圆，而应该在认为该外接圆已经得到的情况下用二分法去逼近其半径。对于N条边不能构成凸多边形的情况亦可进行处理。

虽然已经解决掉了这个求圆半径的问题，但仍然有一个疑问萦绕在脑海之中：给定N个边，一定能够组成凸多边形吗？如果能组成凸多边形，那么不同的组成方式是否会形成不同的外接圆，继而给寻找最大外接圆带来困难呢？

1.凸多边形的构成

对于三条边，当最长边短于另外两边之和时即可构成三角形。

那么类似的，在凸多边形中，除最长边以外的其余边显然短于其他边的长度和。而对于最长边，从其一个端点出发，连接其余各点，可以构成N-2个三角形。

通过递推可以得到结论：N条边构成凸多边形的前提是最长边短于其余边的长度和。与三角形的情况类似，可以注意到该条件的充要性。

2.最大外接圆的存在性与唯一性

凸多边形不一定存在外接圆，题目不对凸多边形是否有外接圆进行讨论，而只在外接圆存在的情况下考虑最大外接圆问题。此时不妨设对于给定的能构成凸多边形的N条边的一个连接序列K₁，存在一个外接圆C。

现考虑外接圆上任意三个连续的顶点A，B，C。若AB=BC，则ABC为等腰三角形，交换AB与BC不改变图形的形状。其他情况下，作AC的中垂线，则在圆周上取B关于中垂线的对称点B’，连接AB’和B’C，可以注意到AB’C是凸多边形上相邻两条边的局部镜像，并不使外接圆发生任何变化。即交换凸多边形上任意两条相邻边并不改变外接圆的大小。

因此，若存在该外接圆C，那么因N条边的全部连接序列K_N均可通过有限次的相邻边交换得到，故以任意顺序相连的N条边都可以内接于该外接圆C上。

再证唯一性，三点即可确定唯一的圆。故该外接圆C是唯一的外接圆，所谓的最大外接圆正是凸多边形唯一的外接圆C。

结论

综上，我们可以认为题目中的求外接圆半径问题是一个求唯一确定且存在的圆的半径的问题（或者不能构成凸多边形）。对于这一问题，注意到圆心在多边形内部或边上时，圆心角之和为2π，圆心在多边形外部时，最大圆心角等于其余圆心角之和。基于此对半径进行二分即可求解。

（二分的边界可能是存在问题的，例如三角形的两边之和无限接近第三边时外接圆的半径趋于正无穷。但此处不予考虑。）

代码

输入形式为正整数边数N，后跟N个边长的值，用空格或换行相隔。
当不能构成多边形时输出：“Cannot construct!”。
当能构成多边形且存在最大外接圆时输出：“Radius:RR”，其中RR为半径，保留两位小数。

#include <math.h>
#include <stdio.h>
const double Pi = acos(-1.0);
//圆周率
const double eps = 1e-5;
//精度
//圆半径为r时计算圆心角总和
double angles_sum(double edges[], int n, double r) {
double sum = 0.0;
for (int i = 0; i < n; i++)
sum += 2 * asin(edges[i] / (2 * r));
return sum;
}
int main() {
int n = 0;
// 边数n
//边长数组edges、圆心角总和sum、最大圆心角max_angle、最大边长max_edge、周长C
double edges[100000] = {0.0}, sum, max_angle, max_edge = 0.0, C = 0.0;
if (scanf("%d", &n))
//输入边数
for (int i = 0; i < n; i++)
if (scanf("%lf", &edges[i]) == 1) {
C += edges[i];
//计算周长
if (edges[i] > max_edge)
max_edge = edges[i];
//记录最长边
}
//不能构成凸多边形
if (max_edge > (C - max_edge)) {
printf("Cannot construct!");
return 0;
}
//计算圆心角总和，直径为最长边
sum = angles_sum(edges, n, max_edge / 2);
if (fabs(sum - 2 * Pi) < eps)
//总和为2π则返回
printf("Radius:%.2f", max_edge / 2);
else {
//二分法下界left，上界right，中值mid，除去最大角的圆心角总和other_angles
double left = max_edge / 2, right = 10000000, mid = 0.0,
other_angles = 0.0;
//循环求解至误差范围内
while (right - left > eps) {
mid = (left + right) / 2;
//计算中值
max_angle = 2 * asin(max_edge / (2 * mid));
//求r=mid时最大圆心角
sum = angles_sum(edges, n, mid);
//求r=mid时圆心角总和
other_angles = sum - max_angle;
//求除去最大角的圆心角总和
if (other_angles > Pi) {
//圆心在多边形内
if (sum > 2 * Pi)
left = mid;
//半径偏小
else
//半径偏大
right = mid;
} else if (other_angles - max_angle < 0)
//圆心在多边形外，半径偏小
left = mid;
else
//圆心在多边形外，半径偏大
right = mid;
}
printf("Radius:%.2f", mid);
//输出最大半径
}
return 0;
}