(* 이 글은 개인적인 접근 과정을 담은 거라 많은 비효율성이 있을 수 있음)


문제 : https://www.acmicpc.net/problem/11392


재미있었지만 끔찍했던 기하 문제,, 게다가 이게 제가 푼 첫 기하 문제였기에 기념삼아 글을 써보려 해요

이 문제를 간단히 요약하자면 원 또는 삼각형을 순차적으로 평면에 올릴 때 이전에 배치된 도형의 가려지는 면적을 어떻게 update하는가? 를 묻고 있어요


처음에는 아이디어가 안떠올라 막막해서 PS갤 찬스를 써서 갤에 글을 올려봤는데 이 문제의 출제 의도가 그린 정리라는 정보를 들었어요


여기서 그린 정리란 미적분학에 나오는 정리인데..

라고 하면 벌써부터 의욕떨어지니 간단히 빙 돌아오는 폐곡선 (볼록 오목 관계없이)의 정보만 가지면 내부 면적을 구해낼 수 있다고 합시다.


이 정리의 부산물이 바로 고등학교 1학년 수학 도형 파트때 공부 조금 해본 사람들은 자주 쓰던 사선 공식, 신발끈 공식이에요


우리가 보통 벡터의 외적의 크기는 라고 하는데 이 값은 정확히 삼각형의 넓이의 2배가 되죠

이제 좌표평면의 임의의 다각형이 주어졌다고 하면 그 꼭짓점들과 원점을 전부 이어서 삼각형을 만들어봅시다




이런 식으로요! 그럼 저 다각형의 넓이는 한 방향을 잡고 회전해가며 아까의 삼각형들을 차례로 외적해서 더하면 구할 수 있어요.

이게 바로 그린 정리에서 Q = x, P = -y 로 잡은 것의 결과와 동일하죠! 그 결과를 다각형 에 적용하면




바로 친숙했던 그 사선 공식이 나옵니다! 여기서 절댓값을 취해주는 이유는 바로 외적이 시계 방향이냐 반시계 방향이냐에 따라서 부호가 달라지기 때문이에요.

(이걸로 https://www.acmicpc.net/problem/11758 이 문제를 거저 먹을 수 있겠죠? 무려 골드 5)


이제 임의의 다각형이 주어졌을 때 넓이를 알 수 있다고 해봅시다. 그럼 다시 문제로 돌아와서 이걸 적용시킬 수 있을까요?

음.. 일단 순수하게 삼각형만 놓고 생각하면 단순 폴리곤 교차 알고리즘(Sutherland–Hodgman)을 쓸 수 있겠지만 문제는 원이네요.


색종이를 포개는 과정에서 오목하게 안 파여있다고(convex) 보장할 수도 없고, 구멍이 뚫릴 수도 있을 뿐더러(수학적으론 not simple) 잘린 면이 곡면일 수도 있는 괴상한 다각형의 넓이를 구할 수 있을까요?




(끔찍하지만 실제로 충분히 테스트케이스로 나올 수 있는 모양입니다!)


음... 많이 어려워보이네요. 처음 제가 접근했던 방식은 삼각형의 변을 지나는 직선을 기준으로 피자 자르듯이 다 잘라버리면 되지 않을까? 였어요

그럼 적어도 convex임을 보장할 수는 있을테니까요. 다만 그러면 조각들이 파편화된다는 문제가 생기게 되죠.. 잘려진 조각들을 레이어마다 하나하나 관리해줘야 된다는 문제도 있고, 잘려진 조각들끼리 또 겹치는지 충돌 판정을 통해 알아내야 하니까요.


무엇이 되든 저세상 구현 난이도에 (Oriented bounding box, rotating calipers, 임의의 유사 다각형(원의 곡면까지 포함된) 안에 점이 포함되었는지, 파편화를 최소화하게끔 자를 방법의 휴리스틱까지!) TLE가 날 게 뻔한 풀이였기에, 그냥 이쪽은 생각을 접기로 했어요.


그럼 어떻게 접근할 수 있을까요? 확실한 건 임의의 다각형에 대한 그린 정리는 아닌 거 같아요. 몇가지 관찰을 해봅시다.


1. 원과 삼각형 사이의 교점은 중요하다.

2. rotation이 각각 지멋대로인 임의의 다각형들로 뭘 해보려는 심산은 접는 게 좋다. 그럼 쓰기 쉽고 절대적인 하나의 회전축이 있어야 하지 않을까?


물론 그린 정리가 미적분학에 속하긴 하다만 태그에 미적분학이 달려있는 걸 보면, 꼭 다각형 그린 정리만이 능사는 아니란 걸 1번과 2번 관찰을 통해 파악할 수 있습니다. 바로 우리가 넓이를 구할 때 많이 쓰는 리만 적분(고교 수준에서의 적분)을 생각해볼 수 있겠죠!


리만 적분은 바로 이 1번 관찰과 2번 관찰에 아주 부합합니다. 적분에는 절대적인 x축과 y축을 기준으로 하고, 교점들의 x좌표를 전부 적분 구간으로 보면 구간 사이에는 수평 곡선만 남기 때문에 위쪽부터 차례대로 적분해서 더해주고 빼주고 하는 식의 포함-배제 원리도 쉽게 적용할 수 있고, 교점들의 x좌표를 좌표 압축할 수도 있는 효과까지 얻을 수 있기 때문이죠.


그래서 제 첫 풀이는 심플하게 xray를 찍어보자는 접근이였습니다. 모든 교점들을 x축으로 사영시키고 모은 다음 좌표 압축을 한 뒤 얻어낸 구간들에 대하여, 구간별로 y = +∞ 방향에서 아래로 투과시켜서 적분 순서를 얻어내는 방식이었죠. 이 발상은 우리가 잘 알고 있는 임의의 점이 다각형에 속하는지 알아내는 알고리즘과 유사합니다.




바로 이런식이에요. 저렇게 투사시켜서 위 적분과 아래 적분을 계산한 후, 포함-배제 원리에 따라 +, -, +, -, ..를 매겨 더해주면 되는 것이었죠.


그럼 우리에게 주어지는 구현 목표는 다음과 같습니다.


1. 선분-선분, 선분-원, 원-원 교점 찾기

2. 각 구간마다의 겹침 여부에 따라 부호 매겨주기

3. [a, b] 구간이 주어졌을 때 원과 삼각형의 리만 적분 구하기

4. 레이어마다 더해서 넓이 구해주기


1번은 아래의 링크를 보고 그대로 구현해주시면 됩니다. 제가 구현할 때 참고한 레퍼런스들이에요


선분-선분 : https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

원-원 : https://stackoverflow.com/questions/3349125/circle-circle-intersection-points

선분-원 : https://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm


이제 이걸 모조리 구현했더니 결과는 뭐.. 당연히 TLE였습니다. 여기서 PS갤 찬스를 한 번 더썼는데 어떤 친절한 유동분(121.135)께서 시간복잡도를 분석해주셨더라구요.


색종이를 올리는 과정 레이어 추가:

ㄴ 추가된 레이어와 이전 도형 사이의 교점 개수 찾기:


그러면 적분 구간은 총 개가 생기게 된다.


적분 구간 마다

ㄴ 구간 사이의 수평 곡선들 개를 순서대로 소팅하는데 드는 시간:

ㄴ 포함-배제 원리를 적용하는 시간(1차원 수직선에서 start time과 end time이 주어졌을 때 cover 여부 탐색):

ㄴ 각 페이즈별로 레이어마다 넓이 갱신:


총 의 더러운 풀이였고, TLE가 생길 여지는 충분했었습니다. 유동님 조언대로 페이즈 별로 넓이를 갱신하는 과정을 prefix sum으로 바꿔도 이라 통과하기엔 많이 힘들죠.


즉, 추가적인 최적화 방법을 더 고안해내야 한다는 2차 목표가 주어집니다. 그래도 답이 맞는지조차 테스트해볼 수도 없는 암흑같은 상황에서 짜리 풀이를 발견한 건 그나마 다행이겠죠? 교차 검증이라도 할 수 있을테니까요


그럼 첫 풀이의 비효율성을 분석해봅시다.



첫 풀이에선 모든 교점이란 교점은 다 찾아서 사영시켜버렸기 때문에 적분 구간이 굉장히 많아진다는 문제가 있었습니다.


우리가 접근했던 리만 적분을 이용한 포함-배제 방식을 사용한다치면 단지 B.x에서 E.x, F.x까지 적분하면 될 것을 다른 도형들의 교점들에 영향을 받아 모조리 쪼개서 적분해야된다는 게 가장 큰 비효율성이죠..


이는 모든 교점을 다 모으지 말고 각 도형마다의 교점만 구해주고, 그 교점들이 만들어내는 사영 구간마다 접근하는 식으로 해결할 수 있습니다.


그래서 제출한 결과는.. 틀렸습니다! WA! 입니다. 그래도 아까의 구리지만 답은 일단 뱉어내는 풀이로 교차검증할 수 있었습니다.


그 결과, 풀이에서 고려하지 않은 점은 다음과 같았습니다.


- 같은 원이 완전히 포개어지면 포함-배제 원리를 어떻게 처리할 것인가?

- 마찬가지로 삼각형의 변이 포개어지면 포함-배제 원리를 어떻게 처리할 것인가?


에 대한 부호 지정 예외처리를 하지 않았기에 틀렸더라구요.


저는

1. 현재 적분이 윗적분인지 아랫적분인지,

2. 삼각형의 두 변이 경우 위에서 포개지는 경우인지 아래에서 포개지는 경우인지

(하나는 위, 하나는 아래로 포개어지면 그건 교차 영역이 없는 경우)


를 확인하고, 적절히 예외처리를 해준 거 같아요!



그렇게 교차검증도 완벽하게 답이 일치했고 기쁜 마음에 제출해본 결과.. 또 틀렸습니다! WA! 를 받았습니다..... 맞왜틀 당해서 좀 많이 혼란스러웠어요


그래서 반쯤 넋놓고 막 초기값도 바꿔보고 무지성 제출해봤는데 몬가 이상하더라구요. 분명히 답이 틀렸으면 같은 퍼센테이지에서 틀렸습니다가 떠야 되는데, 어떨 땐 78%, 어떨 땐 85% 이래서 "아 이거 10^-8 실수 오차 문제구나" 눈치 까고 double를 전부 long double로 바꿔버렸어요.


그랬더니 결과는..



AC.


사용되는 개념은 사실 고등학교 수학정도였지만 발상이 어렵고.. 구현도 어려운.. 기하학 문제(덤으로 실수 오차까지)라서 루비 2를 받은 듯해요. 아무튼 이로써 한동안 기하문제는 풀고 싶지 않을 거 같네요..


그래도 재미가 있었다!