BOJ 2893 - XOR 도형

image.png

포함 배제의 원리임은 쉽게 알 수 있지만 그걸로 단위 정사각형에 포함되는 개수만 세는 문제만 풀어봐서 이렇게 범위가 큰 문제는 어떻게 풀지 몰랐었다.

어떤 벤다이어 그램을 고려한다.

image.png

하나의 원으로만 만들 수 있는 부분은 그냥 더해주면 된다.

겹치는 부분의 넓이가 AA라 할 때,

어떤 원 두개가 겹치는 부분을 보면 정답에 2A2A를 빼줘야한다.

원이 두 개만 있을 때 2A2A를 빼야 한다는 사실을 고려하면 된다.

그럼 세개가 겹칠때를 보자. 3A3A 를 빼줘야 할까?

아니다. 그 부분은 결과적으로 +1+1 이 되어야 올바른데, 22A2^2A 를 더해줘야 한다.

즉 어떤 겹치는 부분에 대해 현재 관여하는 원의 개수가 CC 라면 2C1(1)C12^{C-1} \cdot (-1)^{C-1} 를 곱해줘야 한다.

NN이 작으므로 O(2N)O(2^N)에 모든 삼각형 쌍들의 교집합을 고려해줄 수 있다.

겹치는 부분도 항상 동일한 모양의 직각 이등변삼각형이 나옴을 이용해 영역의 넓이를 특수한 기하학없이 구해낼 수 있다.

x,y,rx, y, r 이 있다면 대각선 직선의 방정식은 x+y=cx+y=c 로 표현할 수 있고 c=x+y+rc=x+y+r 이다.

어떤 두 삼각형의 겹치는 부분을 고려할 때

Max(x1,x2)+Max(y1,y2)<Min(c1,c2)\text{Max}(x_1,x_2)+\text{Max}(y_1,y_2) < \text{Min}(c_1,c_2) 가 성립되야 겹치는 부분이 존재한다.

Tags:

Categories:

Updated:

Comments