最小圆覆盖

Smiling-Weeping / 2023-08-19 / 原文

Smiling & Weeping

　　　　　　　　　　　　　　　　　---- 终于明白，有些路，只能一个人走。

　　　　　　　　　　　　　　　　　　那些邀约好同行的人，一起相伴雨季，

　　　　　　　　　　　　　　　　　　走过年华，但有一天终究会在某个渡口离散。

题目链接：https://www.luogu.com.cn/problem/P1742

题目简介：

# 最小圆覆盖

## 题目描述

给出N个点，让你画一个最小的包含所有点的圆。

## 输入格式

第一行一个整数 $N$ 表示点的个数。

接下来 $N$ 行每行两个实数 $x_i,y_i$ 表示点的坐标。最多两位小数。

## 输出格式

第一行一个实数表示圆的半径。

第二行两个实数表示圆心的坐标。

本题开启 spj，您的答案与标准答案误差不超过 $10^{-9}$ 时，视为正确。

## 样例 #1

### 样例输入 #1

```
6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0
```

### 样例输出 #1

```
5.0000000000
5.0000000000 5.0000000000
```

## 提示

对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$|x_i|,|y_i|\leq 10^4$。

2022.2.26 添加 spj

Talk is cheap , show me the code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define eps 1e-8
 4 const int N = 1e5+1;
 5 int sgn(double x){
 6     if(fabs(x) < eps) return 0;
 7     return x<0 ? -1 : 1;
 8 }
 9 struct Point{double x , y;};
10 double Distance(Point A, Point B){
11     return hypot(A.x-B.x , A.y-B.y);
12 }
13 Point circle_center(const Point a, const Point b, const Point c){
14     Point center;
15     double a1 = b.x-a.x , b1=b.y-a.y , c1=(a1*a1+b1*b1)/2;
16     double a2 = c.x-a.x , b2=c.y-a.y , c2=(a2*a2+b2*b2)/2;
17     double d = a1*b2 - a2*b1;
18     center.x = a.x+(c1*b2-c2*b1)/d;
19     center.y = a.y+(a1*c2-a2*c1)/d;
20     return center;
21 }
22 void min_cover_circle(Point *p , int n , Point &c, double &r){
23     random_shuffle(p , p+n);
24     c=p[0]; r=0;
25     for(int i = 1; i < n; i++){
26         if(sgn(Distance(p[i],c)-r) > 0) // 点p在圆外面
27         {
28             c=p[i]; r=0;
29             for(int j = 0; j < i; j++){
30                 if(sgn(Distance(p[j],c)-r)>0){
31                     c.x = (p[i].x+p[j].x)/2;
32                     c.y = (p[i].y+p[j].y)/2;
33                     r = Distance(p[j] , c);
34                     for(int k = 0; k < j; k++){
35                         if(sgn(Distance(p[k],c)-r) > 0) //两点不能确定圆，就三个点
36                         {
37                             c = circle_center(p[i] , p[j] , p[k]);
38                             r = Distance(p[i] , c);
39                         }
40                     }
41                 }
42             }
43         }
44     }
45 }
46 Point p[N];
47 int main()
48 {
49     int n;
50     scanf("%d",&n);
51     for(int i = 0; i < n; i++)
52         scanf("%lf%lf",&p[i].x,&p[i].y);
53     Point c; double r;
54     min_cover_circle(p,n,c,r);
55     printf("%.10f\n%.10f %.10f\n",r,c.x,c.y);
56     return 0;
57 }