[Python] 22770번 Ellipse Intersection

 

 

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

22770번: Ellipse Intersection

---

 

22/12/31

 

 

전형적인 수학문제로, 극좌표로 적분을 해야하는 문제이다.

 

극좌표 적분에 관한 내용은 미적분학을 배웠다면 알 수 있는 내용이다.

 

근데 이 문제가 꽤나 정밀한 계산을 요구하는지, 식을 정리하지 않으면 틀렸습니다를 받기가 쉽다.

 

다른 분들은 이분 탐색으로도 풀었다는데, 나는 이분 탐색으로도 시도해봤으나 실패해버려서 식정리를 통해 계산하는 방식으로 바꾸었다.

 

(+ 이글을 읽는다면, PC화면으로 읽는 것을 권장한다.)

---

 

문제 접근 방식:

 

 

 

먼저 이 문제의 조건을 살피면, 다음과 같이 3가지 조건으로 나뉜다는 사실을 알 수 있다.

 

케이스 분류

만약 주어지는 입력을 $a, b, c, d$라고 하면, $x$축이 장축인 타원은 $\frac{x^2} {a^2} + \frac{y^2} {b^2} = 1$로 표현할 수 있다.

 

마찬가지로, $y$축이 장축인 타원은 $\frac{x^2} {c^2} + \frac{y^2} {d^2} = 1$로 표현할 수 있다.

 

우리는 $y$축이 장축인 타원을 기준삼아 3가지 경우로 나눌 수 있다.

 

 

첫 번째로, $y$축이 장축인 타원 안에 $x$축이 장축인 타원이 들어가 있는 경우. (즉, $a \leq c$일 때)

 

이 경우, 그림에서는 파란색 타원에 해당이 되며, 이 타원의 넓이만 구해주면 된다. 따라서 $ab\pi$가 된다.

 

 

두 번째로, $x$축이 장축인 타원 안에 $y$축이 장축인 타원이 들어가 있는 경우. (즉, $d \leq b$일 때)

 

이 경우, 그림에서는 빨간색 타원에 해당이 되며, 이때는 겹치는 부분이 검은색 타원이므로, 이 타원의 넓이만 구해주면 된다. 따라서 $cd\pi$가 된다.

 

 

마지막으로, 가장 흔한 경우인데, 두 타원이 교점을 가지는 경우는 극좌표를 이용한 적분을 통해 구할 수 있다.

 

위의 그림을 보면, 이중 적분을 통해 타원에서 각도가 $\theta$만큼 돌아간 넓이를 구할 수 있다.

 

타원의 극 방정식은 타원을 직교좌표계에서 극좌표계로 옮기는 과정에서 얻어낼 수 있다.

 

직교 좌표계에서 극 좌표계로 옮길 때에는 $x$대신 $r(\theta) \cos\theta$를, $y$대신 $r(\theta) \sin\theta$를 대입한다.

 

그러면 임의의 타원을 하나 생각해 보자.

 

$$\frac{x^2} {a^2} + \frac{y^2} {b^2} = 1$$

 

이 타원에서 $x$와 $y$대신에 각각의 값들을 넣어서 치환해 보자.

$$x = r(\theta) \cos \theta$$

$$y = r(\theta) \sin \theta$$

 

그러면 식은 다음과 같이 정리된다.

$$[r(\theta)]^2 \left ( \frac{\cos^2\theta} {a^2} + \frac{\sin^2\theta} {b^2} \right ) = 1$$

$$[r(\theta)]^2 = \frac{1} { \frac{\cos^2\theta} {a^2} + \frac{\sin^2\theta} {b^2} } = \frac{a^2 b^2} {b^2 \cos^2\theta + a^2 \sin^2\theta}$$

 

따라서 우리가 구하고자 하는 타원의 일부분의 넓이는 $\int_{0}^{\theta} \frac{1}{2}[r(\theta)]^2 d\theta$이므로, 이를 대입해서 식을 정리하면 다음과 같다.

 

$$\int_{0}^{\theta} \frac{1}{2}[r(\theta)]^2 d\theta = \frac{a^2 b^2} {2} \int_{0}^{\theta} \frac{1}{b^2 \cos^2\theta + a^2\sin^2\theta} d\theta$$

$$\xrightarrow[\cos^2\theta = 1-\sin^2\theta]{using} \ = \frac{a^2 b^2} {2} \int_{0}^{\theta} \frac{1}{(a^2 - b^2)\sin^2\theta + b^2} d\theta$$

$$\xrightarrow[\sec^2\theta]{multiplying} \ = \frac{a^2 b^2} {2} \int_{0}^{\theta} \frac{\sec^2\theta}{(a^2 - b^2)\tan^2\theta + b^2 \sec^2\theta} d\theta$$

$$\xrightarrow[\sec^2\theta = 1 + \tan^2\theta]{using} \ = \frac{a^2 b^2} {2} \int_{0}^{\theta} \frac{\sec^2\theta}{a^2 \tan^2\theta + b^2} d\theta$$

$$\xrightarrow[t = \tan\theta]{substitute} \ = \frac{a^2 b^2} {2} \int_{0}^{\tan\theta} \frac{1}{a^2 t^2 + b^2} dt$$

$$\xrightarrow[\ from \ denominator]{factor \ a^2} \ = \frac{b^2} {2} \int_{0}^{\tan\theta} \frac{1}{t^2 + \frac{b^2}{a^2}} dt$$

 

이 상황에서, 적분 공식

$$\int\frac{1}{x^2 + a^2}dx = \frac{1}{a} \tan^{-1} \left ( \frac{x}{a} \right ) + C$$

를 이용하여 정리하면,

 

$$\frac{ab} {2} \tan^{-1}\left ( \frac{a}{b} \tan\theta \right )$$

이 나오게 된다.

 

이 공식을 이용하여 문제를 해결해 보자.

 

우리가 구하고자 하는 넓이는 4×((노란색 넓이) + (파란색 넓이))가 된다.

 

먼저 노란색 넓이부터 구해보자.

 

노란색 넓이는 $y$축이 장축인 타원에서 $\theta$만큼을 적분한 값과 같다.

 

$y$축이 장축인 타원은 우리가 $$\frac{x^2} {c^2} + \frac{y^2} {d^2} = 1$$과 같이 쓴다고 했으므로, 위의 공식을 활용하면, $$\mathrm{yellow\ area} = \frac{cd} {2} \tan^{-1}\left ( \frac{c}{d} \tan\theta \right )$$가 된다.

 

파란색 넓이는 $x$축이 장축인 타원을 사등분 한 넓이의 값(파란색 + 노란색 + 보라색)에서 $x$축이 장축인 타원을 $\theta$만큼을 적분한 값(노란색 + 보라색)을 빼면 구할 수 있다.

 

따라서, 파란색 넓이는 다음과 같다.

$$\mathrm{blue\ area} = \frac{ab\pi}{4} - \frac{ab} {2} \tan^{-1}\left ( \frac{a}{b} \tan\theta \right )$$

 

이를 통해 4×((노란색 넓이) + (파란색 넓이))의 값을 구하면 다음과 같다.

$$\mathrm{total\ area} = 2cd \tan^{-1}\left ( \frac{c}{d} \tan\theta \right ) + ab\pi - 2ab \tan^{-1}\left ( \frac{a}{b} \tan\theta \right )$$

 

 

이제 $\tan\theta$의 값을 구하면 된다.

 

이는 아래와 같은 연립방정식을 통해 구할 수 있다.

$$\left\{\begin{matrix}\frac{x^2}{a^2}+\frac{y^2}{b^2}=1\\ \frac{x^2}{c^2}+\frac{y^2}{d^2}=1 \end{matrix}\right.$$

 

식을 정리하면,

$$\frac{x^2} {a^2} + \frac{y^2} {b^2} = \frac{x^2} {c^2} + \frac{y^2} {d^2}$$

$$\frac{x^2} {a^2} - \frac{x^2} {c^2} = \frac{y^2} {d^2} - \frac{y^2} {b^2}$$

$$x^2\left ( \frac{c^2 - a^2} {c^2a^2} \right ) = y^2\left ( \frac{b^2 - d^2} {b^2d^2} \right )$$

$$x\sqrt{\frac{c^2 - a^2} {c^2a^2}} = y\sqrt{\frac{b^2 - d^2} {b^2d^2}}$$

$$\tan\theta = \frac{y}{x} = \sqrt{\frac{\frac{c^2-a^2} {c^2a^2}} {\frac{b^2-d^2} {b^2d^2}}} = \sqrt{\frac{b^2d^2(c^2-a^2)} {c^2a^2(b^2-d^2)}}$$가 된다.

 

 

이 $\tan\theta$의 값을 위의 식에 집어넣으면 아래와 같이 정돈된 식으로 작성할 수 있다.

 

$$\mathrm{total\ area} = 2cd \tan^{-1}\left ( \sqrt{\frac{b^2(c^2-a^2)} {a^2(b^2-d^2)}} \right ) + ab\pi - 2ab \tan^{-1}\left ( \sqrt{\frac{d^2(c^2-a^2)} {c^2(b^2-d^2)}} \right )$$

 

math모듈을 사용하여 a, b, c, d의 값이 주어진다면, 이 값을 계산하여 출력하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 22770번 Ellipse Intersection
# 기하학, 미적분학
from math import *
def solve(a, b, c, d):
    if a > c and b < d:
        p = 2*c*d*atan(b*sqrt((a**2-c**2)/(d**2-b**2))/a)
        q = pi*a*b - 2*a*b*atan(d*sqrt((a**2-c**2)/(d**2-b**2))/c)
        return p+q
    elif b >= d:
        return c*d*pi
    elif a <= c:
        return a*b*pi
for _ in range(int(input())):
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    print(solve(a, b, c, d))