/* ACM ICPC 2002 HAKODATE Problem H 2001/11/18 Kikuchi Yusuke Tokyo Institute of Technology : toridock */ #include #include /* ACM ICPC 対策 計算幾何ライブラリ */ #include #include /* ●実数がゼロであるか判定 引数 x in 実数 戻り値 1 ゼロである 0 ゼロではない */ #define fzero(x) (fabs(x)<1e-9) /* ●ゼロベクトルかどうか判定 引数 v in ベクトル */ int isZeroVector(double v[3]) { return fzero(v[0]) && fzero(v[1]) && fzero(v[2]); } void copyVector(double d[3], double s[3]) { int i; for (i = 0; i < 3; i++) { d[i] = s[i]; } } /* ●2つのベクトルの差をとる v = a-b 引数 v out ベクトルの差 a,b in 差を取るベクトル */ void subVector(double v[3], double a[3], double b[3]) { int i; for (i = 0; i < 3; i++) { v[i] = a[i] - b[i]; } } /* ●ベクトルのノルムの2乗を計算 引数 v in ベクトル */ double norm_2(double v[3]) { double d = 0.0; int i; for (i = 0; i < 3; i++) { d += v[i] * v[i]; } return d; } /* ●2点の距離の2乗を計算する 引数 a, b in 2点の座標 戻り値 2点の距離の2乗 */ double distance_2(double a[3], double b[3]) { double v[3]; subVector(v, a, b); return norm_2(v); } /* ●ベクトルの外積 (EXTerior PRODuct) 引数 c out aとbの外積 = a X b a,b in 外積を取るベクトル 戻り値 なし */ void extProd(double c[3], double a[3], double b[3]) { int i, j, k; for (i = 0; i < 3; i++) { j = (i+1) % 3; k = (i+2) % 3; c[i] = a[j]*b[k] - a[k]*b[j]; } } /* ●ベクトルの内積 (INner PRODuct) 引数 a,b in 内積を取るベクトル 戻り値 ベクトルの内積 */ double inProd(double a[3], double b[3]) { int i; double r = 0.0; for (i = 0; i < 3; i++) { r += a[i] * b[i]; } return r; } /* ●3次正方行列の行列式を計算 引数 a in 3x3正方行列 戻り値 行列式 det(A) */ double det3(double (*a)[3]) { double d = 0.0; int i; for (i = 0; i < 3; i++) { d += a[0][i] * a[1][(i+1)%3] * a[2][(i+2)%3]; d -= a[0][i] * a[1][(i+2)%3] * a[2][(i+1)%3]; } return d; } /* ●クラメルの公式で連立3元1次方程式を解く a00 a01 a02 x0 b0 ( a10 a11 a12 ) (x1) = (b1) a20 a21 a22 x2 b2 引数 x out 解の行ベクトル a in 係数行列 b in 定数項の行ベクトル 戻り値 1 ... 成功 0 ... 失敗 */ int cramer3(double x[3], double (*a)[3], double b[3]) { double d, t[3]; int i, j; d = det3(a); if (fzero(d)) return 0; d = 1.0 / d; for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { t[j] = a[j][i]; a[j][i] = b[j]; } x[i] = det3(a) * d; for (j = 0; j < 3; j++) { a[j][i] = t[j]; } } return 1; } /* ●2点を垂直二等分する(2点からの距離が等しい)平面を計算する 引数 a,b out 平面方程式の係数 p1,p2 in 2点の座標 戻り値 なし p1, p2 が同じ座標の時は、 a,b はすべて 0.0 になる */ void bisector(double a[3], double *b, double p1[3], double p2[3]) { int i; *b = 0.0; for (i = 0; i < 3; i++) { a[i] = p1[i] - p2[i]; *b += p1[i]*p1[i] - p2[i]*p2[i]; } *b *= 0.5; } /* ●3点を通る平面を計算する 引数 a,b out 平面方程式の係数 p0,... in 3点の座標 */ void point3Plane(double a[3], double *b, double p0[3], double p1[3], double p2[3]) { double v1[3], v2[3]; subVector(v1, p1, p0); subVector(v2, p2, p0); extProd(a, v1, v2); *b = inProd(a, p0); } /* ●点が平面上にあるか判定 引数 p in 点の座標 a,b in 平面方程式の係数 戻り値 1 平面上にある 0 平面上にない */ int isPointOnPlane(double p[3], double a[3], double *b) { return fzero(inProd(p, a) - *b); } /* ●2つのベクトルが平行かどうか判定 引数 v1,v2 in ベクトル */ int isParallel(double v1[3], double v2[3]) { double t[3]; extProd(t, v1, v2); return isZeroVector(t); } double x[40][3], center[3]; double r_2, min_r_2; int n_star; void test(int i0, int i1, int i2, int i3) { int i; r_2 = distance_2(x[i0], center); if (r_2 >= min_r_2) return; for (i = 0; i < n_star; i++) { /* x[i0],x[i1],x[i2],x[i3] は球に接しているものとしてテストしない */ if (i == i0 || i == i1 || i == i2 || i == i3) continue; /* 一応、1e-12 程度のエラーは許容しておく */ if (distance_2(center, x[i]) - r_2 > 1e-12) return; } min_r_2 = r_2; // printf("%f %f %f, %f\n", center[0], center[1], center[2], r_2); } int main() { int i, j, k, l; double pa[3], pb, a[3][3], b[3]; while (scanf("%d", &n_star) == 1) { if (n_star == 0) break; /* read data */ for (i = 0; i < n_star; i++) { for (j = 0; j < 3; j++) { scanf("%lf", &x[i][j]); } } min_r_2 = 1e10; for (i = 0; i < n_star-1; i++) { for (j = i+1; j < n_star; j++) { /* 2 points */ /* 2点の真ん中を中心にとる */ for (k = 0; k < 3; k++) { center[k] = (x[i][k] + x[j][k]) * .5; } test(i, j, i, i); for (k = j+1; k < n_star; k++) { /* 3 points */ point3Plane(pa, &pb, x[i], x[j], x[k]); if (!isZeroVector(pa)) { /* 3点を通る円の中心をとる */ copyVector(a[0], pa); b[0] = pb; bisector(a[1], &b[1], x[i], x[j]); bisector(a[2], &b[2], x[i], x[k]); cramer3(center, a, b); test(i, j, k, i); /* 4 points */ for (l = k+1; l < n_star; l++) { if (!isPointOnPlane(x[l], pa, &pb)) { /* 4点を通る球の中心をとる */ bisector(a[0], &b[0], x[i], x[l]); cramer3(center, a, b); test(i, j, k, l); } } } } } } printf("%.5f\n", sqrt(min_r_2) + 0.0000001); } return 0; }