스위핑 알고리즘
- 이벤트 포인트 생성:
- 각 직사각형의 시작점과 끝점을 이벤트로 추가합니다. 시작점은 활성화된 상태로, 끝점은 비활성화된 상태로 처리합니다.
python
def calculate_area(rectangles):
events = [] # 이벤트 포인트를 저장할 리스트 초기화
# 각 직사각형의 이벤트 포인트 생성
for x1, y1, x2, y2 in rectangles:
events.append((x1, y1, y2, 1)) # 시작점 이벤트: (x1, y1, y2, 1)
events.append((x2, y1, y2, -1)) # 끝점 이벤트: (x2, y1, y2, -1)
- 이벤트 정렬:
- x좌표를 기준으로 이벤트를 정렬하여 순차적으로 처리할 수 있도록 합니다.
# 이벤트 포인트를 x좌표 기준으로 정렬
events.sort()'
- 활성 구간 관리:
- 현재 활성화된 y좌표 범위를 리스트로 관리. calculate_y_length 함수는 이러한 범위에서 총 길이를 계산합니다.
# 현재 활성화된 y좌표 범위를 관리할 리스트
active_intervals = []
last_x = 0 # 이전 x좌표를 저장하기 위한 변수
total_area = 0 # 총 면적을 저장할 변수
- 면적 계산:
- 각 이벤트를 처리하면서 x좌표의 변화에 따른 면적을 계산합니다. 이전 x좌표와 현재 x좌표 사이의 폭과 현재 활성화된 y좌표 범위의 길이를 곱하여 면적을 누적합니다.
def calculate_y_length(intervals):
# 주어진 y좌표 범위에서의 총 길이를 계산
if not intervals:
return 0 # 활성 구간이 없으면 길이는 0
intervals.sort() # y좌표 범위를 정렬
total_length = 0 # 총 길이를 저장할 변수
current_start, current_end = intervals[0] # 첫 번째 범위를 초기화
# 나머지 범위를 순회하며 총 길이 계산
for start, end in intervals[1:]:
if start > current_end: # 비활성 구간일 경우
total_length += current_end - current_start # 현재 범위의 길이를 추가
current_start, current_end = start, end # 현재 범위를 업데이트
else: # 겹치는 구간일 경우
current_end = max(current_end, end) # 최대 끝점을 업데이트
total_length += current_end - current_start # 마지막 범위의 길이를 추가
return total_length # 총 길이 반환
- 활성 구간 업데이트:
- 시작점일 경우 y좌표 범위를 추가하고, 끝점일 경우 해당 범위를 제거합니다.
for x, y1, y2, typ in events:
# 면적 계산
if last_x != 0: # 첫 번째 이벤트가 아닐 경우
width = x - last_x # x좌표 변화량 (현재 x - 이전 x)
height = calculate_y_length(active_intervals) # 활성 y좌표 범위의 총 길이
total_area += width * height # 면적 계산 및 누적
# 활성 구간 업데이트
if typ == 1: # 시작점 이벤트
active_intervals.append((y1, y2)) # y좌표 범위를 활성화
else: # 끝점 이벤트
active_intervals.remove((y1, y2)) # y좌표 범위를 비활성화
last_x = x # 현재 x좌표를 이전 x좌표로 업데이트
return total_area # 전체 면적 반환
