[알고리즘] 슈타이너 내접타원 / 마든 정리

(알고리즘보단 수학에 가까운 내용인데 백준문제 풀다가 나와서 알고리즘 카테고리에 정리하겠습니다.)

 

백준 문제 풀다가 재밌고 신기한 정리가 있어서 정리하고자 한다.

 

문제는 여기

https://www.acmicpc.net/problem/2710

2710번: 삼각형 정원

 

슈타이너 내접타원

https://en.wikipedia.org/wiki/Steiner_inellipse

Steiner inellipse - Wikipedia

슈타이너 내접타원은 삼각형에 내접하는 타원이다.

여기에 여러가지 성질이 있다.

 

- 어떤 삼각형에서 슈타이너 내접타원은 오직 하나 존재한다.

- 슈타이너 내접타원의 중심은 삼각형의 중심과 같다.

- 슈타이너 내접타원은 삼각형의 각 꼭짓점의 중점을 지난다.

- 슈타이너 내접타원은 슈타이너 외접타원의 절반이다. (장축의 길이와 단축의 길이가 각각 절반이다.)

- 삼각형의 넓이를 $A$, 그 삼각형의 슈타이너 내접타원의 넓이를 $S$라 하면 $S = \frac{\pi}{3\sqrt{3}} A$가 성립한다.

- 정삼각형이면 슈타이너 내접타원은 원이다.

 

마든 정리

https://ko.wikipedia.org/wiki/%EB%A7%88%EB%93%A0_%EC%A0%95%EB%A6%AC

마든 정리 - 위키백과, 우리 모두의 백과사전

이게 뭔 소리여

마든 정리를 이용하면 두 초점을 구할 수 있는데 이를 통해 슈타이너 내접타원의 방정식을 구할 수 있다.

 

삼각형 $A(x_1,y_1), B(x_2,y_2), C(x_3,y_3)$의 슈타이너 내접타원을 구해보자.

삼각형의 좌표를 복소수로 바꾼다.

그럼 $a = x_1+y_1i, b=x_2+y_2i, c = x_3+y_3i$가 된다.

 

복소방정식 $p(z) = (z-a)(z-b)(z-c)$를 정의하면 $p'(z)=0$의 두 해가 초점의 좌표이다. (같으면 원)

$p(z) = z^3 - (a+b+c)z^2 + (ab+bc+ca)z- abc $

$p'(z) = 3z^2-2(a+b+c)z+ab+bc+ca$

 

근의공식을 사용하자.

$z_1 = \frac{(a+b+c) + \sqrt{(a+b+c)^2-3(ab+bc+ca)}}{3}, z_2 = \frac{(a+b+c)-\sqrt{(a+b+c)^2-3(ab+bc+ca)}}{3}$

$z_1 = u_1+v_1i, z_2 = u_2+v_2i$라고 하면 슈타이너 내접타원의 초점은 $P(u_1, v_1), Q(u_2, v_2)$가 된다.

 

초점을 구했고 지나는 한 점(삼각형의 중점)을 알았으니 방정식도 구할 수 있게 됐다.

 

위 백준같은 문제는 두 초점으로부터 타원까지 이르는 거리의 합도 구하라고 했으니 이것도 쉽게 구할 수 있다.

---

정리를 처음 이해했을때 "이게 왜 됨?"반응이 절로 나왔다.

증명은 아직 안봤지만 내용이 너무 신기해서 언젠가 시간나면 봐야겠다.

 

골드급 정리는 아닌것 같아서 플래티넘으로 기여했다...