（1）实数的输入和输出。几何坐标值一般是实数，编程时用double类型，不用精度较低的float。double类型读入时用%lf格式，输出时用%f格式。

（2）实数的精度判断。实数做浮点数运算会产生精度误差，为了控制精度，可以设置一个偏差值eps（epsilon）。判断一个浮点数是否等于0，不能直接用“==0”来判断，而是用sgn()函数，判断是否小于eps。比较2个浮点数时，也不能直接用“==”判断是否相等，而是用dcmp()函数判断是否相等。eps要大于浮点运算结果的不确定量，一般取10-8。如果eps取10-10，可能会有问题。下面是代码。

const double pi = acos(-1.0);          //圆周率，精确到15位小数：3.141592653589793
const double eps = 1e-8;               //偏差值，有时用1e-10，但是要注意精度
int sgn(double x){                     //判断x的大小
if(fabs(x) < eps)  return 0;       //x==0，返回0
else return x<0?-1:1;              //x<0返回-1，x>0返回1
}
int dcmp(double x, double y){          //比较两个浮点数 
if(fabs(x - y) < eps)   return 0;  //x==y，返回0
else return x<y ?-1:1;             //x<y返回-1，x>y返回1
}

圆也是二维几何的内容，本文首先给出圆的基本定义和计算，然后介绍重要应用——最小圆覆盖。

01、圆基本的定义和计算

1. 圆的定义

用圆心和半径表示圆。

struct Circle{
    Point c;      //圆心
    double r;     //半径
    Circle(){}
    Circle(Point c,double r):c(c),r(r){}
    Circle(double x,double y,double _r){c=Point(x,y);r = _r;}
};

2. 点和圆的关系

根据点到圆心的距离判断点和圆的关系。

int Point_circle_relation(Point p, Circle C){
    double dst = Distance(p,C.c);
    if(sgn(dst – C.r) < 0) return 0;       //0 点在圆内
    if(sgn(dst – C.r) ==0) return 1;       //1 圆上
    return 2;                               //2 圆外
}

3. 直线和圆的关系

根据圆心到直线的距离判断直线和圆的关系。

int Line_circle_relation(Line v,Circle C){
    double dst = Dis_point_line(C.c,v);
    if(sgn(dst-C.r) < 0) return 0;     //0 直线和圆相交
    if(sgn(dst-C.r) ==0) return 1;     //1 直线和圆相切
    return 2;                               //2 直线在圆外
}

4. 线段和圆的关系

根据圆心到线段的距离判断线段和圆的关系。

int Seg_circle_relation(Segment v,Circle C){
    double dst = Dis_point_seg(C.c,v);
    if(sgn(dst-C.r) < 0) return 0;      //0线段在圆内
    if(sgn(dst-C.r) ==0) return 1;      //1线段和圆相切
    return 2;                           //2线段在圆外
}

5. 直线和圆的交点

求直线和圆的交点，如图1所示，先求圆心c在直线上的投影q，再求得距离d，然后根据r和d求出长度k，最后求出两个交点图片，其中n为直线的单位向量。

■ 图1 直线和圆的交点

//pa, pb是交点。返回值是交点个数
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
    if(Line_circle_relation(v, C)==2)  return 0;//无交点
  Point q = Point_line_proj(C.c,v);          //圆心在直线上的投影点
     double d = Dis_point_line(C.c,v);          //圆心到直线的距离
  double k = sqrt(C.r*C.r-d*d);    
    if(sgn(k) == 0){                            //1个交点，直线和圆相切
     pa = q;  pb = q;  return 1;
}
Point n=(v.p2-v.p1)/ Len(v.p2-v.p1);       //单位向量
pa = q + n*k;  pb = q - n*k;
return 2;                                  //2个交点
}

02、最小圆覆盖

最小圆覆盖问题：给定n个点的坐标，求一个半径最小的圆，把n个点全部包围，部分点在圆上。

常见的算法有两种：几何算法、模拟退火算法。本文只介绍几何算法，如果数据规模不大，还可以用模拟退火算法求解。

这个最小圆可以由n个点中的两个或3个点确定。两点定圆时，圆心是线段AB的中点，半径是AB长度的一半，其他点都在这个圆内。如果两点不足以包围所有点，就需要三点定圆，此时圆心是A、B、C这3个点组成的三角形的外心，如图2所示。

■ 图2 两点定圆和三点定圆

一般用增量法求最小圆覆盖。算法从一个点开始，每次加入一个新的点，更新最小圆，直到扩展到全部n个点。设前i个点的最小覆盖圆为Ci，过程如下。

(1) 加入第1个点p1。C1的圆心就是p1，半径为0。

(2) 加入第2个点p2。新的C2的圆心是线段p1 p2的中心，半径为两点距离的一半。这一步操作是两点定圆。

(3) 加入第3个点p3。有两种情况：p3在C2的内部或圆周上，不影响原来的最小圆，忽略p3；p3在C2的外部，此时C2已不能覆盖所有3个点，需要更新。下面讨论p3在C2外部的情况。因为p3一定在新的C3上，现在的任务转换为在p1、p2中找一个点或两个点，与p3一起两点定圆或三点定圆。重新定圆的过程，相当于回到步骤(1)，把p3作为第1个点加入，然后再加入p1、p2。

(4) 加第4个点p4。分析和步骤(3)类似，为加强理解，这里重复说明一次。如果p4在C3内部或圆周上，忽略它；如果在C3外部，那么需要求新的最小圆，此时p4肯定在新的C4的圆周上。任务转换为在p1、p2、p3中找一个点或两个点，与p4一起构成最小圆。先检查能不能找到一个点，用两点定圆；如果两点不够，就找到第3个点，用三点定圆。重新定圆的过程和前3步类似，即把p4作为第1个点加入，然后加入p1、p2、p3。

(5) 持续进行下去，直到加完所有点。

算法思路概括如下。

假设已经求得前i-1个点的Ci-1，现在加入第i个点，有以下两种情况：

(1) i在C i-1的内部或圆周上，忽略i；

(2) i在C i-1的外部，需要求新的C i。首先，i肯定在C i上，然后重新把前面的i-1个点依次加入，根据两点定圆或三点定圆，重新构造最小圆。

现在分析最小圆覆盖的几何算法的复杂度。例8.7给出了模板代码。其中，有3层for循环，看起来复杂度似乎是O(n3)。不过，如果点的分布是随机的，用概率进行分析可以得出，程序的复杂度接近O(n)。在代码中，用random_shuffle()函数进行随机打乱。例如，如果前两个点p1 和p2恰好就是最后的两点定圆，那么其他点都只需要检查一次是否在C2内就可以了，程序在第1层for循环就结束了。
● 例8.7最小圆覆盖(洛谷P1742)

问题描述： 输入n个点的坐标，求最小圆覆盖。

输入： 第1行输入一个整数n，表示点的个数。后面n行中，每行输入两个实数，表示点的坐标。

输出： 第1行输出一个实数，表示圆的半径。第2行输出两个实数，表示圆心的坐标。保留10位小数。

下面给出最小圆覆盖的几何代码。circle_center()函数求三角形abc的外接圆的圆心，min_cover_circle()函数返回最小覆盖圆的圆心c和半径r。

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int N = 1e5+1;
int sgn(double x){
    if(fabs(x) < eps)  return 0;
    else return x<0?-1:1;
}
struct Point{ double x, y; };
double Distance(Point A, Point B){return hypot(A.x-B.x,A.y-B.y);}
Point circle_center(const Point a, const Point b, const Point c){
    Point center;
    double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2;
    double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2;
    double d =a1*b2-a2*b1;
    center.x =a.x+(c1*b2-c2*b1)/d;
    center.y =a.y+(a1*c2-a2*c1)/d;
    return center;
}
void min_cover_circle(Point *p, int n, Point &c, double &r){
    random_shuffle(p, p + n);             //随机函数，打乱所有点。这一步很重要
    c=p[0]; r=0;                          //从第1个点p0开始。圆心为p0，半径为0
    for(int i=1;i<n;i++)                  //扩展所有点
        if(sgn(Distance(p[i],c)-r)>0){    //点pi在圆外部
            c=p[i]; r=0;                  //重新设置圆心为pi，半径为0
            for(int j=0;j<i;j++)          //重新检查前面所有的点。
                if(sgn(Distance(p[j],c)-r)>0){   //两点定圆
                    c.x=(p[i].x + p[j].x)/2;
                    c.y=(p[i].y + p[j].y)/2;
                    r=Distance(p[j],c);
                    for(int k=0;k<j;k++)
                        if (sgn(Distance(p[k],c)-r)>0){   //两点不能定圆，就三点定圆
                            c=circle_center(p[i],p[j],p[k]);
                            r=Distance(p[i], c);
                        }
                }
        }
}
Point p[N];  
int main(){
    int n; cin >> n;
    for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    Point c; double r;                  //最小覆盖圆的圆心和半径
    min_cover_circle(p,n,c,r);
    printf("%.10f\n%.10f %.10f\n",r,c.x,c.y);
    return 0;
}