Common Tangent Hyperplanes of K Spheres

In the year 2233 of the Weishek Era, humanity discovered a new technology: using quantum mechanical principles, signals from a cosmic broadcast station on Earth can be transmitted at super‐light speed to a tangent hyperplane of Earth. Centuries later, after the Gravity Ark seeded human civilization among three planets in a vast X galaxy, these broadcast devices finally found renewed use: real‑time interplanetary communication.

The planet chief, Amoeba, now faces a tougher challenge. Besides the 3‑planet case, he needs you to solve the K‑dimensional version: given K spheres (which may degenerate to points, that is, their radii can be zero) in a K‑dimensional space (with K ≤ 10 since the Universe plus time has 11 dimensions), find all the common tangent hyperplanes shared by these spheres.

A hyperplane (of dimension K − 1) is defined as the set of points equidistant from two given points. A hyperplane is tangent to a sphere if it touches the sphere at exactly one point, and it is a common tangent if it is tangent to every one of the K spheres.

You are guaranteed that the input is such that there is a finite (nonzero) number of common tangent hyperplanes. (In general, for the nondegenerate case the expected number is 2^K.)

Mathematical Definitions

• Distance: In K-dimensional space, the distance between two points A=(a₀,a₁,…,a_K−1) and B=(b₀,b₁,…,b_K−1) is \[ |AB| = \sqrt{\sum_{i=0}^{K-1} (a_i - b_i)^2}. \]
• Sphere: The set of points in K-dimensional space at a fixed distance (the radius r) from a center point. (For K=2 this is the familiar circle.)
• Hyperplane: In K-dimensional space, the set of points equidistant from two given points. (For K=2 this is a straight line – the perpendicular bisector.)
• Tangent Hyperplane: A hyperplane that intersects a sphere at exactly one point.
• Common Tangent Hyperplane: A hyperplane that is tangent to all of the given spheres.

Hint:

Represent the hyperplane in normalized form as \[ a \cdot x = b,\] with \(a = (a_0, a_1, \dots, a_{K-1})\) a unit vector. The tangent condition for the i-th sphere with center \(c_i\) and radius \(r_i\) is \[ |a \cdot c_i - b| = r_i. \] Subtracting the equation for the first sphere from the others eliminates \(b\) and yields a linear system in \(a\) (up to a scaling factor). The requirement \(\|a\|=1\) then produces a quadratic equation which results in a finite number of solutions. Also note that if \(a \cdot x = b\) is a solution then so is \((-a) \cdot x = -b\), which represent the same hyperplane provided that a unique normalization rule is applied (for example, ensuring that the first nonzero component of \(a\) is positive).

Task: Given an integer K (K ≥ 2) on the first line followed by K lines describing the spheres in K-dimensional space (each sphere is described by K real numbers for its center coordinates followed by a real number for its radius), print all common tangent hyperplanes. First output an integer M indicating the number of hyperplanes found (which, in the generic case, is \(2^K\)). Then output M lines, each containing K+1 real numbers corresponding to \(a_0, a_1, \dots, a_{K-1}, b\) of a hyperplane. Each hyperplane must be in normalized form, with \(\|a\|=1\) and with the sign of \(a\) normalized as described above. Answers within an absolute error of 10⁻⁶ will be accepted.

inputFormat

The first line contains an integer \(K\) (\(K \ge 2\)). The following \(K\) lines each contain \(K+1\) space‐separated real numbers. In the i‑th of these lines, the first \(K\) numbers represent the coordinates of the center of the i‑th sphere, and the last number is its radius. (Note that a sphere may be degenerate, i.e. its radius may be zero.)

outputFormat

First, output an integer \(M\) representing the number of common tangent hyperplanes found. Then output \(M\) lines, each containing \(K+1\) space‑separated real numbers \(a_0, a_1, \dots, a_{K-1}, b\) which describe a hyperplane in the normalized form \[ a \cdot x = b. \] Print your answers with an absolute error of at most 10⁻⁶.

sample

2
0 0 1
3 0 1

4
0.000000 1.000000 1.000000
0.000000 -1.000000 -1.000000
1.000000 0.000000 1.000000
-1.000000 0.000000 -1.000000