직사각형 합집합의 둘레

시간 제한2초메모리 제한128 MB

요약
최대 5000개의 축 정렬 직사각형이 있을 때 그 합집합의 외곽 둘레 길이를 스위프 라인으로 계산하는 문제입니다.
난이도

어려움10점 중 8점

유형
정렬, 기하, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

2차원 평면에 N개의 축에 평행한 직사각형이 주어진다. 모든 직사각형의 합집합을 생각할 때, 그 바깥 경계 전체의 길이를 구하시오. 서로 겹치거나 변을 맞대는 부분은 합집합 내부가 되면 둘레에 포함하지 않는다. N이 0이면 합집합은 비어 있고 답은 0이다.

입력

첫째 줄에 직사각형의 개수 N (0 ≤ N ≤ 5,000)이 주어진다. 다음 N개의 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 점 (x1, y1)과 (x2, y2)는 한 직사각형의 서로 마주 보는 꼭짓점이다. 모든 좌표는 -10,000 이상 10,000 이하이다.

출력

직사각형들의 합집합의 둘레 길이를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
    예상 출력
    228