2개의 점을 지나는 직선, 3개의 점을 지나는 원, 5개의 점을 지나는 원뿔곡선(원, 타원, 포물선, 쌍곡선)의 방정식 찾기

최근에 3개의 점을 지나는 원 (외심과 반지름), 5개의 점을 지나는 원뿔곡선의 방정식을 찾는 것에 대해 구할 일이 생겼는데 생각보다 간단한 트릭이 존재해서 블로그에 써보기로 했습니다.

행렬식 (Determinant)

행렬식은 $\textrm{det}$이라고 쓰이는, $n \times n$ (실수) 행렬에 대해 값이 실수인 함수입니다.

행렬식은 다음과 같은 조건을 만족하도록 정의되는 함수이며, 해당 정의를 만족하는 함수는 $n$에 따라 유일합니다. $A$의 행렬식은 $\textrm{det}(A) = |A|$ 로 작성하기도 합니다.

1. $|I_n| = 1$. 여기서 $I_n$는 항등행렬입니다.
2. 행렬식은 다중 선형사상입니다. 행렬의 한 열을 $r$배 하면, 행렬식의 값도 $r$배가 됩니다. $j$번째 열만 다른 두 행렬 $A$, $B$에 대해서, 두 행렬식 값의 합은 $j$번째 열을 제외하고는 $A, B$와 같고 $j$번째 열이 $A$의 $j$번째 열과 $B$의 $j$번째 열을 합친 $A_j+B_j$인 행렬의 행렬식과 같습니다. 수식으로 쓰면 $\begin{align}|A| &= \big | a_1, \dots, a_{j-1}, r \cdot v + w, a_{j+1}, \dots, a_n | \\ &= r \cdot | a_1, \dots, v, \dots a_n | + | a_1, \dots, w, \dots, a_n | \end{align}$ 입니다.
3. 두 열이 같은 행렬의 행렬식은 $0$입니다. 즉, $| a_1, \dots, v, \dots, v, \dots, a_n| = 0$입니다. 이를 교대사상이라고 합니다.

이를 만족하는 함수 $\textrm{det}$은 $n$에 대해 유일합니다. (이에 대한 증명은 선형대수에 대한 깊은 지식을 요구하므로 생략합니다.)

 

$n = 2$인 구체적인 예와 함께 살펴보도록 합시다.  $\det \begin{pmatrix} a & b \\c & d \end{pmatrix} = \begin{vmatrix} a & b \\c & d \end{vmatrix} = ad - bc$가 성질을 만족하는 함수입니다.

 

행렬식은 다음과 같이 계산됩니다: $\det \begin{pmatrix} 3 & 7 \\1 & -4 \end{pmatrix} = \begin{vmatrix} 3 & 7 \\ 1 & {-4} \end{vmatrix} = (3 \cdot (-4)) - (7 \cdot 1) = -19$

이제 이 함수가 성질을 만족하는지 구체적인 예와 함께 살펴봅시다.

1. $\begin{vmatrix} 1 & 0 \\0 & 1 \end{vmatrix} = 1 \times 1 - 0 \times 0 = 1$ 입니다.
2. $\begin{vmatrix} a & rb +e \\ c & rd + f \end{vmatrix} = a(rd+f) - (rb+e)c = ard+af-(rbc+ec) = r(ad-bc)+(af-ec) = r \begin{vmatrix} a & b \\c & d \end{vmatrix} + \begin{vmatrix} a & e \\ c & f \end{vmatrix} $ 입니다. 첫번째 열을 바꾼 경우에도 비슷하게 성립합니다.
3. $\begin{vmatrix} a & a \\ b & b \end{vmatrix} = ab - ab = 0$입니다.

 

여러개의 점을 지나는 직선 / 원 / 원뿔곡선의 방정식을 찾기 위해 우리는 다중 선형사상과 교대 사상의 성질을 이용할 것입니다.

2개의 점을 지나는 직선의 방정식

직선의 방정식은 다음과 같은 일반적인 형태를 가지고 있습니다: $f(x, y) = Ax + By + C = 0$

이 함수는 $\begin{pmatrix} x \\ y \end{pmatrix}$에 대한 선형사상은 아닙니다. $C$는 $x, y$에 대해 비례하게 움직이지 않기 때문입니다. 선형사상인 함수를 만들기 위해 $C = C \cdot 1$이기 때문에, $1$을 포함시켜서 선형사상으로 만드는 방법을 사용할 것입니다. 이제 함수 $L(x, y, z) = Ax+By+Cz$를 생각합시다. 이 함수는 다음 성질을 만족합니다.

•  $f(x, y) = L(x, y, 1)$
• $L(x, y, z)$는 $\begin{pmatrix} x \\ y \\ z \end{pmatrix}$에 대한 선형사상입니다. 즉, $L(rx_a+x_b, ry_a+y_b, rz_a + z_b) = rL(x_a, y_a, z_a) + L(x_b, y_b, z_b)$입니다.

이제 이 함수가 두 점 $(x_1, y_1)$ 및 $(x_2, y_2)$을 지나야 한다고 합시다. 즉, $L(x_1, y_1, 1) = L(x_2, y_2, 1) = 0$인 $L$을 찾아야합니다. 우리는 행렬식의 교대 사상의 성질을 사용합니다. 행렬식에 똑같은 두 벡터가 있으면 값이 $0$입니다.

 

이를 위해서 행렬식의 각 열에 지나야하는 두 점에 해당하는 열벡터를 써줍시다. $L'(x, y, z) = \begin{vmatrix}x & x_1 & x_2 \\ y & y_1 & y_2 \\ z & 1 & 1\end{vmatrix}$과 같은 식을 생각합시다.

• $(x, y, 1) = (x_1, y_1, 1)$이거나 $(x, y, 1) = (x_2, y_2, 1)$인 경우 같은 두 열이 있기 때문에 $L'(x_1, y_1, 1) = L'(x_2, y_2, 1) = 0$입니다.
• $L'(x, y, z)$는 $\begin{pmatrix} x \\ y \\ z \end{pmatrix}$에 대한 선형사상입니다.

그러므로 우리는 $f(x, y) = L'(x, y, 1) = \begin{vmatrix}x & x_0 & x_1 \\ y & y_0 & y_1 \\ 1 & 1 & 1\end{vmatrix}$이 우리가 찾는 직선의 방정식이라는 것을 알 수 있습니다. 

 

실제로 이 함수를 계산하기 위해서는 행렬식을 전개하면 됩니다. 이를 위해 첫번째 열에 대해 여인자 전개를 사용하면 (나중에 글로 작성하겠습니다.)

\[
\begin{aligned}
L(x,y)
&=
\begin{vmatrix}
x & x_0 & x_1 \\
y & y_0 & y_1 \\
1 & 1 & 1
\end{vmatrix} \\
&= x\begin{vmatrix} y_0 & y_1 \\ 1 & 1 \end{vmatrix}
- y\begin{vmatrix} x_0 & x_1 \\ 1 & 1 \end{vmatrix}
+ 1\begin{vmatrix} x_0 & x_1 \\ y_0 & y_1 \end{vmatrix} \\[6pt]
&= x(y_0 - y_1) - y(x_0 - x_1) + (x_0y_1 - x_1y_0).
\end{aligned}
\]

가 됩니다. 정리하면 $f(x,y) = (y_0 - y_1)x + (x_1 - x_0)y + (x_0y_1 - x_1y_0) = 0$ 이 되고, 이것이 점 $(x_0, y_0), (x_1, y_1)$을 지나는 직선의 방정식입니다.

3개의 점을 지나는 원, 5개의 점을 지나는 원뿔곡선의 방정식

 

중심이 $(x_0, y_0)$이고 반지름이 $r$인 원의 방정식은 $(x-x_0)^2 + (y - y_0)^2 = r^2$으로 쓰입니다. 전개하면 $x^2 - 2x_0x + x_0^2 + y^2 - 2y_0y + y_0^2 - r^2 = 0$이 되고, $A = -2x_0, B = - 2y_0, C = x_0^2 + y_0^2 - r^2$ 을 이용해서 다시 쓰면 $f(x, y) = (x^2 + y^2) + Ax + By + C = 0$이 됩니다.

 

2개의 점을 지날때와 비슷한 방법을 사용하면 이는 $\begin{pmatrix}x^2+ y^2 \\ x \\ y \\ 1\end{pmatrix}$에 대한 선형사상으로 표현됨을 알 수 있습니다. 구체적으로는, $S(\alpha, \beta, \gamma, \delta) = K\alpha + A'\beta + B'\gamma + C'\delta$) 로 정의하면, $S(x^2+y^2, x, y, 1) = Kf(x, y)$가 됩니다. 여기서, $A = \frac{A'}{K}, B = \frac{B'}{K}, C = \frac{C'}{K}$를 사용하면 됩니다.

 

즉, $(x_1, y_1); (x_2, y_2); (x_3, y_3)$를 지나는 원의 방정식은 

 

\[
\begin{aligned} f(x,y)
&=
\begin{vmatrix}
x^2 +y^2 & x_1^2 + y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \\
x & x_1 & x_2 & x_3 \\
y & y_1 & y_2 & y_3 \\
1 & 1 & 1 & 1
\end{vmatrix} \end{aligned} = 0 \] 

이 됩니다. 

 

혹시 외접원 중심의 좌표를 외우고싶다면, 여인자 전개를 한 이후 $(x_0, y_0) = \left(-\frac{A}{2}, -\frac{B}{2}\right)$로 계산되는 외접원의 중심을 다음과 같이 삼중곱으로 외우면 좀 더 쉬울수도 있습니다:

$\vec{X} = (x_1, x_2, x_3)$ $\vec{Y} = (y_1, y_2, y_3)$ $\vec{Z} = (x_1^2+y_1^2, x_2^2+y_2^2, x_3^2 + y_3^2)$라고 정의하고 편의상 $\vec{1} = (1, 1, 1)$이라고 쓰면 외접원의 중심은

\[\left( -\frac{1}{2} \cdot \frac{ \vec{1} \cdot \left(\vec{Y} \times \vec{Z} \right) }{ \vec{1} \cdot \left(\vec{X} \times \vec{Y} \right) }, -\frac{1}{2} \cdot \frac{ \vec{1} \cdot \left(\vec{Z} \times \vec{X} \right) }{ \vec{1} \cdot \left(\vec{X} \times \vec{Y} \right) }  \right) \]

으로 표현 가능합니다.

---

비슷하게 원뿔곡선의 방정식은 $Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$이므로, $(x_1, y_1); (x_2, y_2); (x_3, y_3); (x_4, y_4); (x_5, y_5)$를 지나는 원뿔곡선의 방정식은

 

\[
\begin{aligned} f(x,y)
&=
\begin{vmatrix}
x^2 & x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2 \\
xy & x_1y_1 & x_2y_2 & x_3y_3 & x_4y_4 & x_5y_5 \\
y^2 & y_1^2 & y_2^2 & y_3^2 & y_4^2 & y_5^2 \\
x & x_1 & x_2 & x_3 & x_4 & x_5 \\
y & y_1 & y_2 & y_3 & y_4 & y_5 \\
1 & 1 & 1 & 1 & 1 & 1
\end{vmatrix} \end{aligned} = 0 \] 

이 됩니다.

 

여기서부터는 직접 전개를 할 수도 있지만, 프로그램적인 방법으로 행렬식을 계산해서 실제 값을 구하는게 더 좋아보입니다.

연습문제

 

BOJ 7463 - Ellipse

타원의 방정식을 구한 이후, $Ax^2 + Bxy + Cy^2 = 1$인 타원의 넓이가 $\frac{\pi}{\sqrt{AC-B^2/4}}$임을 사용하면 됩니다. 단, $AC-B^2/4 \ge 0$일 경우 타원이 아닙니다.

아래 코드는 stackexchange 질문/답변에서 찾은 타원의 방정식이 주어졌을 때 답을 직접 계산하는 방법을 사용합니다.

코드: http://boj.kr/5e3dcb9c426544e38ee29f3520affa4c

 

BOJ 2389 - 세상의 중심에서...

원의 중심으로 가능한 것은 다음 두 가지 경우 중 하나입니다.

• 두 사람의 중점
• 세 사람 (이상)을 지나는 원의 중심

이 모두를 직접 시도해보면 $\mathcal{O}(N^4)$에 풀 수 있습니다.

코드 (Rust): https://www.acmicpc.net/source/share/003b10d698ad4154b5832cb99053694d

코드 (Python): https://www.acmicpc.net/source/share/8a630706bed04284b4bbab2d76fecf76