일단 답은 얼추 맞는 거 같은데 시간복잡도가..
일단 이 문제에서 아이디어랑 기본적인 관찰은
1. 이 문제에선 원과 삼각형의 교점, 그리고 꼭짓점말곤 별로 중요하지 않다. 이 점들을 '중요점'이라 하자.
2. 중요점들은 전부 x축으로 사영시켜버리고 리만 적분 구간점으로 본다.
(리만 적분이니까 원의 양 끝 x좌표도 중요점에 포함됨)
3. 그러면 중요점 사이엔 교점이 없게 되어, 무조건 변과 변 사이의 영역만 남을 뿐이다
이제 적절히 중요점 사이 구간을 리만 적분한 다음, 서로 빼줘 이 변과 변 사이의 자투리 영역을 구한다.
*4. 각 페이즈별로 레이어의 배치에 따라 자투리 영역을 더해준다
인데..
이게 중요점들의 x축 사영점 개수에 따라 시간복잡도가 폭증하거든
특히 4번에서 변과 변 사이의 영역을 전부 카운팅해줘야 해서 너무 많이 잡아먹히는데.. 좋은 방법 없을까?
제가 제대로 이해했다면 교점이나 사영점의 개수는 O(N^2)이고 하나의 리만 적분 구간 [x(i-1), x(i)] 내에는 원호나 선분이 O(N)개가 있는데 이걸 순서대로 정렬하는 데는 O(N lg N)이 들고 그다음에는 1차원 선분이 수직선을 덮고 있는 문제랑 완전히 동일하게 환원되는 것 같아서 O(N). 그러면 전체 시간복잡도가 O(N^2 * N lg N) = O(N^3 lg N)으로 될 수 있을 것 같아요. 코드를 읽어봤는데요, x = a와 어떤 수평곡선 두 개로 둘러싸인 조각의 면적을 riemann이라고 하신 것 같아요. 그런 조각은 O(N^2)개가 있겠죠. 그런데 이걸 "i번째까지 덮었을 때 j번째 도형에 기여하는지 여부"에 따라 일일이 area[i][j]에 더해주시는 것 같아요. 그렇게 되면
제 생각에는 O(N^4)가 나올 것 같아요. 그런데 사실 어떤 조각은 lifetime이라는 게 있어서 i = j번째까지 덮었을 때만 보이고 i = j+1번째부터는 가려지잖아요? 그러면 prefix sum을 이용해서 시간 복잡도를 하나 뗄 수 있죠. 그러면 find_area()가 O(N^3)으로 줄고 전체 시간복잡도가 O(N^3 lg N)으로 돌아올 것 같네요.
헉.. 무지 상세한 설명 감사드려요!! 한번 시도해볼게요
다시 생각해보니까 비슷하긴 한데 조금 부정확했어서 다시 씁니다ㅜㅜ 조각의 개수는 O(N^2)가 아니라 O(N^3)이고 나머지는 마찬가지로 area[i][j]에 일일이 더하는 건 O(N^4) prefix sum을 쓰는 건 O(N^3)입니다.
worst case 하나를 예시를 들자면 N개의 삼각형이 있을 때 삼각형 T_n이 좌표 (0, 0), (N, 0), (n, 1)로 정의되는 경우가 있습니다