쓰는 스타일을 최대한 간결하게 바꿨는데 이전껀 못바꾸겠다..

목표: 도형(원, 다각형)을 순서대로 올려놓을 때 각 색종이의 최종 가시 면적을 계산한다.

핵심: 교차점 기반 x-분할 + 구간별 아래쪽 넓이 누적 + 연결(국소) 업데이트

1) 문제를 푸는 관점

• 도형을 한 장씩 올리며, 새 도형이 기존 도형을 가리는 영역을 정확히 빼 준다.
• 이를 위해 평면을 수직선들로 분할해, 각 x-구간마다 보이는 면적을 더하고 빼며 누적한다.
• 분할만 제대로 하면, 구간 내에서는 경계(선분/원호)의 위·아래 관계가 변하지 않기 때문에 넓이를 정확히 계산할 수 있다.

2) 전처리: “교차점 기반 x-분할”

• 각 색종이들간의 교차점을 전부 구하고, 이 x좌표에 전부 수직선을 긋는다.(원-원, 삼각형-삼각형, 원-삼각형 전부) 그리고 각 삼각형의 경우는 각 꼭짓점, 원의 경우는 원의 가장 왼쪽, 가장 오른쪽에도 추가로 수직선을 그어준다.)

3) 구간별 “아래쪽 넓이”로 더하고 빼기

• 각 도형들을 선분 혹은 원호로만 생각하면 이들은 전부 아래쪽 넓이 조각을 가지고 있다.
• 이를 추가한 곳을 경계로 다른 도형의 넓이들을 빼준다. ex) 넓이를 10(1번도형 시작), 30(2번도형 시작), 50 (2번도형 끝), 70 (1번도형끝) 이라하자. 여기서 15~45에 도형이 추가된다 가정하자. 그러면 15에 추가되서 45에서 끝났으니 1번도형은 15~45전부 가려졌으니 30을 빼줘야하고, 2번도형은 30~45까지만 가려진것이니 15를 빼주면 된다.
• 이를 위해서라면 원래는 새로운 도형의 아래쪽 넓이가 각각 어디에 들어가야하는지 찾기위해, 넓이간 순서를 유지하기 위해 set을 사용해야하지만, 사용하지 않는 방법을 다음 스텝에 소개한다.

4) 자료구조 전략: 정렬(set) 대신 연결리스트 사용

• 단순히 매 구간마다 정렬 자료구조에 넣고 위에서부터 순서를 유지하면 전체가 느려진다.