개요

2014년 05월 31일에 개최된 월파팀 연습대회에서 패배한 Balloonphilia 팀이 벌칙으로 작성하게 된 Editorial이다. 무슨 약을 하셨길래 이런 생각을... 조..좋은제도다

문제 목록

문제 pdf(코드포스)

A. Mixing Colours

B. It Can Be Arranged

C. Shopping Malls

D. Decoding the Hallway

E. Joe is learning to speak

F. Odd and Even Zeroes

G. VivoParc

H. Binary Tree

I. Trending Topic

J. Cleaning the Hallway

이전에 알고스팟에 올라온 CIRCLES문제와 유사하다. 그러나 CIRCLES에서는 N개의 원의 합집합의 넓이를 구하는 것으로 끝이지만 이 문제는 N개의 도넛의 합집합의 넓이를 구해야 하기 때문에 조금 더 많은 예외처리를 필요로 한다.

우선 입력으로 주어진 도넛들에 그린 정리를 적용하기 위해 도넛의 바깥쪽 원과 안쪽 원을 두개의 폐곡선으로 떼어낸다. 그래서 바깥쪽 원은 반시계방향으로 적분, 안쪽 원은 시계방향으로 적분하면 원하는 넓이를 구할수 있게 된다.

이제 어려운 부분은 이 폐곡선들에서 적분하지 말아야 하는 구간을 찾는 것이다. 각각의 폐곡선들과 도넛의 위치관계를 정리하면 아래와 같다.

이제 구간을 잘 구했으면 구간에 속하지 않은 부분을 잘 적분하면 답을 구할 수 있다!