[코딩테스트] N개의 직사각형 중 정확히 두 직사각형에만 속하는 단위 정사각형의 개수

• 문제
  • N(1≤N≤200)개의 직사각형(x1,y1,x2,y2, 좌측하단 좌표와 우측상단 좌표의 tuple)이 주어진다. 이 때 정확히 두 개의 직사각형에만 속하는 단위정사각형의 개수를 구하여라.
• 해설

import sys

number_rectangles = int(sys.stdin.readline())
rectangles = [list(map(int, x.split())) for x in sys.stdin.readlines()]
# number_rectangles = 3
# rectangles = [
#     [1, 1, 4, 4],
#     [3, 2, 5, 5],
#     [2, 5, 4, 6]
# ]

intersecting_number = 2

# Create slices
slices = []
for rectangle in rectangles:
    slices.append(rectangle[1])
    slices.append(rectangle[3])
slices = list(set(slices))
slices.sort()  # O(NlogN), slice는 rectangle 개수에 선형적으로 증가하기 때문

# Determine where the rectangle belonging to slices
rectangles.sort(key=lambda x: x[1])  # O(NlogN)
slice_to_rectangles = {idx: [] for idx in range(len(slices) - 1)}

def binary_search(arr, target, low=None, high=None):  # O(logN)
    low, high = low or 0, high or len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] > target:
        return binary_search(arr, target, low, mid)
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)

previous_start_slice_idx = 0
for idx_rec, rectangle in enumerate(rectangles):  # O(NlogN)
    start_slice_idx = binary_search(slices, rectangle[1], low=previous_start_slice_idx)
    end_slice_idx = binary_search(slices, rectangle[3], low=previous_start_slice_idx) - 1
    for idx_slice in range(start_slice_idx, end_slice_idx + 1, 1):
        slice_to_rectangles[idx_slice].append(idx_rec)
    previous_start_slice_idx = start_slice_idx

# Iterate from slices, left x + 1, right x - 1하여 cumulative sum==k 세기
def get_cumulative_sum(list_of_tuples):
    result = [list_of_tuples[0]]
    cum_sum = list_of_tuples[0][1]
    for tp in list_of_tuples[1:]:
        cum_sum += tp[1]
        result.append((tp[0], cum_sum))
    return result

answer = 0
for idx_slice in range(len(slices) - 1):  # O(N^2 * logN)
    rectangle_idxs = slice_to_rectangles[idx_slice]
    sorted_xs = []
    for rectangle_idx in rectangle_idxs:
        sorted_xs.append((rectangles[rectangle_idx][0], +1))
        sorted_xs.append((rectangles[rectangle_idx][2], -1))
    sorted_xs.sort(key=lambda x: x[0])
    xs_with_cumulative_sum = get_cumulative_sum(sorted_xs)
    for ind, (x, cum_sum) in enumerate(xs_with_cumulative_sum):
        if cum_sum == intersecting_number:
            width = xs_with_cumulative_sum[ind + 1][0] - x
            height = slices[idx_slice + 1] - slices[idx_slice]
            answer += width * height
print(answer)

• 포인트
  • sweep line개념으로 y1좌표를 기준으로 아래에서 위로 line segment 만들어서 접근
  • left는 +1, right는 -1을 두고 cumulative sum으로 intersecting 횟수 세기