[BOJ] 1186. 직사각형 색칠하기

1일 1PS 3일차!

문제

---

골드 4

• 높은 번호를 가진 직사각형이 보이는 것이므로 순서대로 처리
• 사실 많은 조건 분기로 처리하는 것이 정석이지만 겹치는 직사각형의 넓이 총합을 구하는 공식을 그대로 사용하였다

포인트

---

1. 직사각형들과 겹치는 부분을 따로 저장
2. 직사각형 내에서 겹치는 부분의 합을 구하고 전체 넓이에서 뺀다
3. 넓이 순서대로 정렬 후 상위 k 개의 index 뽑아내기

코드

---

def findCommon(sqr1, sqr2):
    if sqr1[0] >= sqr2[2]: return 0
    if sqr1[1] >= sqr2[3]: return 0
    if sqr1[2] <= sqr2[0]: return 0
    if sqr1[3] <= sqr2[1]: return 0

    return [max(sqr1[0], sqr2[0]), max(sqr1[1], sqr2[1]), min(sqr1[2], sqr[2]), min(sqr1[3], sqr[3])]


def find_largest_indices(arr, n):
    if len(arr) == n:
        return range(1, len(arr) + 1)

    indexed_arr = list(enumerate(arr, start=1))
    sorted_arr = sorted(indexed_arr, key=lambda x: x[1], reverse=True)

    top_n_indices = [index for index, value in sorted_arr[:n]]
    top_n_indices.sort()

    return top_n_indices


def calculate_non_overlapping_area(rectangles):
    if not rectangles:
        return 0

    events = []
    for rect in rectangles:
        x1, y1, x2, y2 = rect
        events.append((x1, 1, y1, y2))
        events.append((x2, -1, y1, y2))

    events.sort()

    active_segments = []
    prev_x = events[0][0]
    total_area = 0

    for x, event_type, y1, y2 in events:
        width = x - prev_x
        active_height = calculate_active_height(active_segments)
        total_area += width * active_height

        if event_type == 1:
            active_segments.append((y1, y2))
        else:
            active_segments.remove((y1, y2))

        prev_x = x

    return total_area


def calculate_active_height(segments):
    if not segments:
        return 0

    segments.sort()

    active_height = 0
    current_y1, current_y2 = segments[0]

    for y1, y2 in segments:
        if y1 > current_y2:
            active_height += current_y2 - current_y1
            current_y1, current_y2 = y1, y2
        else:
            current_y2 = max(current_y2, y2)

    active_height += current_y2 - current_y1
    return active_height


n, k = map(int, input().split())

sqr_list = []
common_list = [[] for _ in range(n)]
area = [0 for _ in range(n)]

for i in range(n):
    sqr = list(map(int, input().split()))

    for j in range(len(sqr_list)):
        s = sqr_list[j]
        common = findCommon(s, sqr)
        if common != 0:
            common_list[j].append(common)

    sqr_list.append(sqr)

for i in range(n):
    sqr = sqr_list[i]
    area[i] = (sqr[2] - sqr[0]) * (sqr[3] - sqr[1])

    if common_list[i]:
        area[i] -= calculate_non_overlapping_area(common_list[i])


print(' '.join(map(str,find_largest_indices(area, k))))