C++程序 在一个平面内多个点求最小外接圆算法
时间: 2024-02-05 07:12:54 浏览: 53
求解最小外接圆一般采用 Welzl 算法,其基本思路如下:
1. 随机选择一个点 A,将其作为最小外接圆的圆心。
2. 遍历所有点,如果点在圆内则不做处理,否则将该点作为新的边界点。
3. 对新的边界点进行递归处理,直到所有边界点都处理完成。
下面是 C++ 的实现代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
};
struct Circle {
Point c; // 圆心
double r; // 半径
};
const int MAXN = 1005;
Point A[MAXN];
Circle C;
double dist(Point a, Point b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Circle spanning_circle(int n, int k) {
if (n == 0 || k == 3) {
switch (k) {
case 0: return { {0, 0}, 0 };
case 1: return { A[0], 0 };
case 2: return { { (A[0].x + A[1].x) / 2, (A[0].y + A[1].y) / 2 },
dist(A[0], A[1]) / 2 };
}
}
Circle c = spanning_circle(n-1, k);
if (dist(A[n-1], c.c) > c.r) {
A[k] = A[n-1];
c = spanning_circle(n-1, k+1);
}
return c;
}
Circle min_circle(Point* p, int n) {
random_shuffle(p, p+n);
for (int i = 0; i < n; i++) {
if (dist(p[i], C.c) > C.r) {
C = { p[i], 0 };
for (int j = 0; j < i; j++) {
if (dist(p[j], C.c) > C.r) {
C = { {(p[i].x+p[j].x)/2, (p[i].y+p[j].y)/2}, dist(p[i], p[j])/2 };
for (int k = 0; k < j; k++) {
if (dist(p[k], C.c) > C.r) {
C = spanning_circle(i, 0);
}
}
}
}
}
}
return C;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i].x >> A[i].y;
}
cout << fixed << setprecision(2) << min_circle(A, n).r << endl;
return 0;
}
```
其中,`A` 数组存储所有的点,`C` 结构体存储最小外接圆的圆心和半径。`spanning_circle` 函数用于递归求解最小外接圆,`min_circle` 函数则是主函数,用于调用 `spanning_circle` 函数并返回最小外接圆的半径。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)