For any given triangle, a circle can be circumscribed around it: 
Given the three (x, y) coordinates of a triangle, find the (x, y)coordinates of the center of the circumscribed circle and its radius.
It is guaranteed that all tests have an integer solution.
Example
For
triangle = [[3,2],
[1,4],
[5,4]] the output should be
circumcircle(triangle) = [3, 4, 2].
The circumscribed circle is centered at (3, 4) and has a radius of 2.
Input/Ouput
- [time limit] 4000ms (js)
[input] array.array.integer triangle
Array of three arrays of length 2, where each array represents (x, y) coordinates of triangle's vertices.
It is guaranteed that all three points don't lie on the same line.
Constraints:
triangle.length = 3,
triangle[i].length = 2,
-100 ≤ triangle[i][j] ≤ 100.[output] array.integer
Array of three elements: the first two elements are the (x, y)coordinates of the circumscribed triangle, and the last element is its radius.
Solution
We get 3 points, \(A, B, C\) from which we construct a triangle. In order to find the circumcenter of the triangle, we need to find the point where the perpendicular bisector lines cross. The bisector points on the sides of the triangle can be found like this:
\[ \begin{array}{rl} M_1 &= \frac{1}{2}(B+C)\\ M_2 &= \frac{1}{2}(A+B)\\ M_3 &= \frac{1}{2}(A+C) \end{array} \]
Having a typical rotation-matrix \(R(90^\circ)\), we can rotate the sides of the triangle around the \(M\)-points and get the rotated points plus the line equations. For line one:
\[ \begin{array}{rl} B_{M_1} &= M_1 + R \cdot (B - M_1)\\ C_{M_1} &= M_1 + R \cdot (C - M_1) \end{array} \] \[ L1(s) = B_{M_1} + s(C_{M_1} - B_{M_1}) \]
For line two:
\[ \begin{array}{rl} A_{M_2} &= M_2 + R \cdot (A - M_2)\\ B_{M_2} &= M_2 + R \cdot (B - M_2)\\ \end{array} \] \[ L2(s) = A_{M_2} + s(B_{M_2} - A_{M_2}) \]
For line three:
\[ \begin{array}{rl} A_{M_3} &= M_3 + R \cdot (A - M_3) \\ C_{M_3} &= M_3 + R \cdot (C - M_3)\\ \end{array} \] \[ L3(s) = A_{M_3} + s(C_{M_3} - A_{M_3}) \]
We now calculate the intersection point of two of these lines, since all three lines meet in the same point anyway. I devoted a small article to the derivation of line intersections, which we will use here. The circumcenter \(O\) can be calculated with
\[O=v_1 + s \cdot w_1\]
As a small reminder, the parameter \(s\) can be calculated like this:
\[ \left(\begin{array}{c} s\\ t \end{array}\right) = \left(\begin{array}{cc} w_1 & -w_2 \end{array}\right)^{-1}\cdot\left(\begin{array}{c} v_2-v_1\end{array}\right)\]
The four remaining values are already present, but when simplified we get:
\[\begin{array}{rl} v_1 & = B_{M_1}\\ & = M_1 + R \cdot (B - M_1)\\ & = \frac{1}{2}(B+C) + R\cdot \frac{1}{2}(B-C)\\ w_1 & = C_{M_1} - B_{M_1}\\ & = M_1 + R \cdot (C - M_1) - (M_1 + R \cdot (B - M_1))\\ & = R \cdot (C - B)\\ v_2 & = A_{M_2}\\ & = M_2 + R \cdot (A - M_2)\\ & =\frac{1}{2} (A + B) + R \cdot \frac{1}{2} (A - B)\\ w_2 & = B_{M_2} - A_{M_2}\\ & = M_2 + R \cdot (B - M_2) - (M_2 + R \cdot (A - M_2))\\ & = R \cdot (B - A) \end{array}\]
We now need to work on the intersection part. First the inverse expression:
\[ \left(\begin{array}{cc} w_1 & -w_2 \end{array}\right)^{-1} = \frac{1}{A_xB_y - A_yB_x - A_xC_y + A_yC_x + B_xC_y - B_yC_x} \left(\begin{array}{cc} A_x - B_x & A_y - B_y\\ C_x - B_x & C_y - B_y\\ \end{array}\right) \]
Now the second factor:
\[ \left(\begin{array}{c} v_2-v_1\end{array}\right) = \left(\begin{array}{c} A_x/2 - A_y/2 + B_y - C_x/2 - C_y/2\\ A_x/2 + A_y/2 - B_x + C_x/2 - C_y/2 \end{array}\right) \]
And finally, we can calculate the \(s\) parameter. Everything else from the expression can be ignored.
\[ \left(\begin{array}{c} s\\ t \end{array}\right)=\frac{1}{w}\left(\begin{array}{c} x \\ y \end{array}\right) \]
With
\[x=((A_y - B_y)((A_x + A_y + C_x - C_y)/2 - B_x)) - ((A_x - B_x)((A_y - A_x + C_x + C_y)/2 - B_y))\]
\[y=((B_x - C_x)((A_y - A_x + C_x + C_y)/2 - B_y)) - ((B_y - C_y)((A_x + A_y + C_x - C_y)/2 - B_x))\]
\[w=A_xB_y - A_yB_x - A_xC_y + A_yC_x + B_xC_y - B_yC_x\]
After finding possible pairs and simplifications, the final obfuscated solution looks like this:
circumcircle = t => {
b = t[0]
c = t[1]
g = t[2]
a = b[0]
b = b[1]
d = c[0]
c = c[1]
f = g[0]
e = g[1]
k = a * a + b * b
l = d * d + c * c
m = f * f + e * e
o = c - e
p = e - b
q = b - c
h = a * o + d * p + f * q
g = k * o + l * p + m * q
d = k * (f - d) + l * (a - f) + m * (d - a)
h+= h
g = g / h - a
d = d / h - b
return [g+a, d+b, Math.hypot(g, d)]
} This code can be simplified even further:
circumcircle = t => {
a = t[0][0]
b = t[0][1]
c = t[1][0] - a
d = b - t[1][1]
e = t[2][0] - a
f = t[2][1] - b
g = 2 * (c * f + e * d)
o = c * c + d * d
p = e * e + f * f
h = (o * f + p * d) / g
i = (p * c - o * e) / g
return [h + a, i + b, Math.hypot(h, i) | 0]
}