[18968] Circle Union

 아마 1학기 기말고사 기간에 풀었던 걸로 기억하는 문제. 푼 지는 꽤 됐는데 언젠가 글을 써야지 써야지 하다가 이제서야 쓴다.

 

 covered region을 최대화하려면 각 원이 모두 한 점에만 만나야 한다. 그러니까 모든 원(과 원 안의 부분)을 이루는 점의 집합의 교집합의 원소가 정확히 한 개여야 한다는 것이다. 그렇지 않은 경우엔 원 하나를 적절히 움직여서 더 넓은 covered region을 갖는 형태로 만들 수 있다. 그러면 원점을 지나는 원들의 형태를 다루는 문제가 된다. 정확히는 형태라기보다는 원의 중심이 존재하는 위치? 각도? 그런 것이다.

 

 이제 문제 상황을 좀 편하게 다루기 위해 도형을 극좌표계로 펼쳐 보자. 극좌표계에서 원점을 지나고 반지름이 $R$인 원은 $r = 2R\cos(\theta - a)$ 꼴로 표현된다. 여기서 $a$는 원이 원점 기준 반시계 방향으로 회전한 각도이다. 그러면 우리가 다루는 모든 원이 $\theta - r$ 평면에 그려진, 코사인 그래프의 $-\pi /2 ~ \pi /2$ 부분이 된다. 이 코사인 부분들을 가로로 막 움직이면서 전체 넓이를 최대화하면 된다.

 

 여기서부터 증명은 못 하고 그냥 직관의 영역. 언젠가는 증명할 수 있을지도? 아직은 못함.

원이 많이 주어진 상황에서 무조건 원들은 일부 겹칠 수밖에 없다. 그렇기에 겹치는 넓이를 최소화하는 것이 전체 넓이를 가장 크게 만드는 방법인데...

코사인 부분 세 개가 나란히 있다고 하자. 양 끝의 코사인 부분은 고정되어 있을 때 가운데 코사인 부분을 어떻게 두어야 셋의 부분 넓이를 가장 크게 만들 수 있을까 생각하면, 왼쪽 부분 가운데 부분이 만나는 점의 $r$값과 가운데 부분 오른쪽 부분이 만나는 점의 $r$값이 같도록 하면 된다는 것을 알 수 있다. 이유는 다음과 같은데,

 1. 가운데 코사인 부분을 위에서 말한 대로 배치한 뒤의 양 교점 $r$값이 $R_0$이라고 하자.

 2. 이제 가운데 코사인 부분을 $\text{d}\theta$만큼 아주아주아주 살짝 오른쪽으로 옮긴다. 

 3. 오른쪽 부분과 만나는 $r$값이 $R_r$, 왼쪽 부분 값이 $R_l$로 바뀌었다고 하자. 그러면 충분히 작은 $\text{d}\theta$값에 대해 오른쪽 부분과 더 겹치게 된 넓이는 $\text{d}\theta \cdot (R_0+R_r)/2$, 왼쪽 부분과 안 겹치게 된 넓이는 $\text{d}\theta \cdot (R_0+R_l)/2$이다.

 4. 그러면 전체 넓이는 안 겹치게 된 넓이 - 더 겹치게 된 넓이$ = \text{d}\theta \cdot \{(R_0+R_l)/2 - (R_0+R_r)/2\} = \text{d}\theta \cdot (R_l - R_r)/2$만큼 변화한다

 5. 여기서 $R_l - R_r$의 부호를 생각해 보자. 오른쪽 부분과 가운데 부분이 만나는 점이 왼쪽 부분과의 그것보다 가운데 부분의 봉우리에 더 가까이 있게 되기 때문에 $R_r$이 $R_l$보다 더 크다. 따라서 전체 넓이는 줄어든다.

 6. 가운데 코사인 부분을 왼쪽으로 옮긴다고 해도 똑같은 결과가 나온다. 즉 원래의 상태가 최적의 상태가 된다.

 7. 이게 직교좌표계에서 구한 넓이긴 한데 극좌표계에서 생각해도 결과는 다르지 않다. 어차피 직관으로 하는 거니까...

 

그러니까 한 코사인 부분이 다른 코사인 부분들과 만나는 점의 높이가 같도록 해야 한다는 것인데, 이 코사인 부분들은 쭉 늘어져 있으니까 다음과 같이 된다.

 1. a-b 교점의 높이와 b-c 교점의 높이를 같도록 해야 한다.

 2. b-c 교점의 높이와 c-d 교점의 높이를 같도록 해야 한다. 그러면 a-b높이 = b-c높이 = c-d높이.

 3. c-d와 d-e -> a-b = b-c = c-d = d-e

 ...

 n. 모든 코사인 부분들이 만드는 교점은 같은 높이에 있어야 한다!

 

 그리고 이렇게 생각하면 원들을 늘어놓는 순서도 의미가 없는 것이 어차피 일정 높이까지는 다 같이 겹치는 것이고 그 위의 부분들은 모두 겹치지 않기 때문에 똑 떼서 순서를 바꾼들 넓이에는 영향이 없다.

 

 이제 높이 하나를 정하면 그걸로 코사인들 쭉 이어걸어서 넓이를 구할 수 있다. 정답 높이는 식 써서 찾아도 되고 그냥 이분 탐색 때려도 나온다.

 

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

18968번: Circle Union