BOJ 2893 - XOR 도형
포함 배제의 원리임은 쉽게 알 수 있지만 그걸로 단위 정사각형에 포함되는 개수만 세는 문제만 풀어봐서 이렇게 범위가 큰 문제는 어떻게 풀지 몰랐었다.
어떤 벤다이어 그램을 고려한다.
하나의 원으로만 만들 수 있는 부분은 그냥 더해주면 된다.
겹치는 부분의 넓이가 $A$라 할 때,
어떤 원 두개가 겹치는 부분을 보면 정답에 $2A$를 빼줘야한다.
원이 두 개만 있을 때 $2A$를 빼야 한다는 사실을 고려하면 된다.
그럼 세개가 겹칠때를 보자. $3A$ 를 빼줘야 할까?
아니다. 그 부분은 결과적으로 $+1$ 이 되어야 올바른데, $2^2A$ 를 더해줘야 한다.
즉 어떤 겹치는 부분에 대해 현재 관여하는 원의 개수가 $C$ 라면 $2^{C-1} \cdot (-1)^{C-1}$ 를 곱해줘야 한다.
$N$이 작으므로 $O(2^N)$에 모든 삼각형 쌍들의 교집합을 고려해줄 수 있다.
겹치는 부분도 항상 동일한 모양의 직각 이등변삼각형이 나옴을 이용해 영역의 넓이를 특수한 기하학없이 구해낼 수 있다.
$x, y, r$ 이 있다면 대각선 직선의 방정식은 $x+y=c$ 로 표현할 수 있고 $c=x+y+r$ 이다.
어떤 두 삼각형의 겹치는 부분을 고려할 때
$\text{Max}(x_1,x_2)+\text{Max}(y_1,y_2) < \text{Min}(c_1,c_2)$ 가 성립되야 겹치는 부분이 존재한다.
Comments