double angleOf(double x, double y) {
double dist=sqrt(x*x+y*y)
if (y>=0.) return acos( x/dist)
else return acos(-x/dist)+.5*CIRCLE_RADIANS }
// Pass in a set of 2D points in x,y,points. Returns a polygon in polyX,polyY,polyCorners.
//
// To be safe, polyX and polyY should have enough space to store all the points passed in x,y,points.
void findSmallestPolygon(double *x, double *y, long points, double *polyX, double *polyY, long *polyCorners) {
double newX=x[0], newY=y[0], xDif, yDif, oldAngle=.5*CIRCLE_RADIANS, newAngle, angleDif, minAngleDif
long i
// Find a starting point.
for (i=0 i<points i++) if (y[i]>newY || y[i]==newY && x[i]<newX) {
newX=x[i] newY=y[i] }
*polyCorners=0
// Polygon-construction loop.
while (!(*polyCorners) || newX!=polyX[0] || newY!=polyY[0]) {
polyX[*polyCorners]=newX
polyY[*polyCorners]=newY minAngleDif=CIRCLE_RADIANS
for (i=0 i<points i++) {
xDif=x[i]-polyX[*polyCorners]
yDif=y[i]-polyY[*polyCorners]
if (xDif || yDif) {
newAngle=angleOf(xDif,yDif) angleDif =oldAngle-newAngle
while (angleDif< 0. ) angleDif+=CIRCLE_RADIANS
while (angleDif>=CIRCLE_RADIANS) angleDif-=CIRCLE_RADIANS
if (angleDif<minAngleDif) {
minAngleDif=angleDif newX=x[i] newY=y[i] }}}
(*polyCorners)++ oldAngle+=.5*CIRCLE_RADIANS-minAngleDif }}
#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=0i<ni++)
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
*/
