Thursday, January 16, 2014

acmicpc.net 1617 - 허후민

문제 링크(acmicpc.net 1617)

시간복잡도 : O(N^3), 공간복잡도 : O(N)

우선 주어진 입력을 Plane Sweeping한다. : O(N)

각 좌표별로 sweep line을 정렬한다 : O(N log N)

이웃한 x구간, y구간을 지정(O(N^2))한다. 각 x[i]~x[i+1], y[i]~y[i+1]로 이루어진 직사각형 영역에 대해서 N개의 직사각형이 이 구간을 포함하는지를 보면서 넓이를 계산(O(N))한다.(O(N^2 * N) = O(N^3))

넓이를 간단하게 계산하기 위해서는
1) 홀수행 홀수열들의 개수
2) 홀수행 짝수열들의 개수
3) 짝수행 홀수열들의 개수
4) 짝수행 짝수열들의 개수
총 4가지를 s[0]~s[4]로 따로 지정해두고 있으면 편리하다.

k번째 직사각형이 1) ~ 4) 중 포함하는 것이 있다면 각각을 더하고 0으로 바꾸면 이후의 계산에는 포함되지 않아 중복되는 넓이가 생기지 않는다.

Source Code

No comments:

Post a Comment