先说明计算几何中的数值计算问题。计算几何题目的计算量大多是实数，需要处理小数，注意以下两点。
（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;
}
