Question

c语言高手进 这题难！！！！！！！！！！！ 任给出平面上n个点的坐标,试求覆盖这n个点的圆的最小半径

解题思路：只要分别求出所有3点组合覆盖的最小圆，取其中半径最大者即为所求。 那么确定覆盖3点的最小圆的步骤可以如下：
(1) 若3点组成直角或钝角三角形，或3点共线，此时，最小圆的半径为三边中最长边的一半。
(2) 否则，3点组成锐角三角形，最小圆为3点的外接圆。
(3) 外接圆半径计算方法：
(a) 若3点构成一个三角形(即3点不共线)，并设3点的坐标为 (x1,y1)，(x2,y2)，(x3,y3)，求出两点(x1,y1)和(x2,y2)之间的距离L1=sqrt((x1-x2)^2+(y1-y2)^2), 同样求出(x1,y1)和(x3,y3)之间的距离L2，以及(x2,y2)和(x3,y3)之间的距离L3。
(b) 求出三角形半周长L=(L1+L2+L3)/2以及面积S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。
(c) 根据公式4SR=L1*L2*L3，求外接圆半径R=L1*L2*L3/(4*S)。

输入
输入平面点的个数n以及n个点的坐标。

输出
输出覆盖这n个点的最小半径(小数点后保留4位)。
样例输入4
4.2,5.6
78.3,3.8
35.4,15.9
29.88,42.56
样例输出以上4个点的覆盖圆的最小半径为37.1463

Answer 1

#include <stdio.h>
#include <math.h>
// 输入最多的点数目
#define MAX_POINTS_AMOUNT 100

struct Point
{
double x,y;
};
// 求点 p1, p2 的距离
double distance(struct Point p1, struct Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
// 求 a, b, c 中的最大值
double max(double a, double b, double c)
{
return a>=b && a>=c
? a
: b>=a && b>=c
? b
: c;
}

// 判断长度为 a, b, c 的 3条线段能否组成三角形
// 判断依据为：至少有一条边的长度，大于另两条边的长度差（绝对值），小于另两条边的长度和
int canMakeTriangle(double a, double b, double c)
{
return a>fabs(b-c) && a<(b+c) ||
b>fabs(a-c) && b<(a+c) ||
c>fabs(a-b) && c<(a+b);
}

// 判断长度为 a, b, c 的 3条线段能否组成锐角三角形
// 判断依据：根据余弦定理，求出 3 个角的余弦值
int canMakeAcuteTriangle(double a, double b, double c)
{
unsigned int i;
double cos_a, cos_b ,cos_c;
if(canMakeTriangle(a, b, c))
{
cos_a = (b*b + c*c - a*a)/(2*b*c);
cos_b = (a*a + c*c - b*b)/(2*a*c);
cos_c = (a*a + b*b - c*c)/(2*a*b);
return cos_a>0 && cos_b>0 && cos_c>0;
}
return 0;
}

/* 求覆盖 n 个点 points 的最小圆的半径
算法：
只要分别求出所有3点组合覆盖的最小圆，取其中半径最大者即为所求。
确定覆盖3点的最小圆的步骤可以如下：
(1) 若3点组成直角或钝角三角形，或3点共线，此时，最小圆的半径为三边中最长边的一半。
(2) 否则，3点组成锐角三角形，最小圆为3点的外接圆。
(3) 外接圆半径计算方法：
(a) 若3点构成一个三角形(即3点不共线)，
并设3点的坐标为 (x1,y1)，(x2,y2)，(x3,y3)，求出两点(x1,y1)和(x2,y2)之间的距离
L1=sqrt((x1-x2)^2+(y1-y2)^2), 同样求出(x1,y1)和(x3,y3)之间的距离L2，
以及(x2,y2)和(x3,y3)之间的距离L3。
(b) 求出三角形半周长L=(L1+L2+L3)/2以及面积S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。
(c) 根据公式4SR=L1*L2*L3，求外接圆半径R=L1*L2*L3/(4*S)。
参数：
n ： 点数目
points ： n 个点的坐标
start ： 递归参数。表示当前从在 n 个点的第 start 个开始选取。初始值为 0。
selectPointsAmount ： 递归参数。表示当前已经选好了的点数。最多为 3 个。初始值为 0。
selectPoints : 递归参数。表示当前已经选好了的点的坐标数组。初始值为 NULL。
返回：
覆盖 n 个点 points 的最小圆的半径。

*/
double minCircleRadius(unsigned int n, struct Point points[],
unsigned int start, unsigned int selectPointsAmount, struct Point selectPoints[])
{
if(n <= 1)
return 0.0;
if(n == 2)
return distance(points[0], points[1])/2.0;
else
{
if(selectPointsAmount == 3)
{// 已经选好了 3 个点，求能覆盖它们的最小圆的半径

double L1 = distance(selectPoints[0], selectPoints[1]);
double L2 = distance(selectPoints[0], selectPoints[2]);
double L3 = distance(selectPoints[1], selectPoints[2]);
double L = (L1 + L2 + L3)/2.0;
double S = sqrt(L*(L-L1)*(L-L2)*(L-L3));
if(canMakeAcuteTriangle(L1, L2, L3))
{// 能组成锐角三角形
return L1*L2*L3/(4.0*S);
}
else
{// 其他情况：三点共线，组成直角三角形，或锐角三角形
return max(L1, L2,L3)/2.0;
}
}
else
{// 任选 3 个点
double r, minR = 0.0;
unsigned int i;

struct Point temp[3];
if(selectPoints == NULL)
selectPoints = temp;

for(i=start;(n-i)>=(3-selectPointsAmount);i++)
{
selectPoints[selectPointsAmount] = points[i];
r = minCircleRadius(n, points, i+1, selectPointsAmount+1, selectPoints);
if(minR < r)
minR = r;
}
return minR;
}
}
}
int main(int argc, char *argv[])
{
struct Point points[MAX_POINTS_AMOUNT];
unsigned int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf,%lf",&points[i].x, &points[i].y);
printf("%.4lf\n",minCircleRadius(n, points, 0, 0, NULL));
}
return 0;
}
/*
4
4.2,5.6
78.3,3.8
35.4,15.9
29.88,42.56
*/