가짜 부동산

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

요약

실수 좌표를 가진 최대 5000개의 직사각형이 주어질 때, 겹치는 부분을 한 번만 세어 합집합의 넓이를 구하고 소수점 둘째 자리까지 반올림해 출력한다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 분할 정복, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

부정직한 땅 주인이 넓은 직사각형 모양의 땅(구획)들을 팔고 있습니다. 그런데 여러 구획이 서로 겹쳐 있어서, 사실상 같은 땅을 여러 번 판매하고 있습니다. 이것은 진짜 부동산(real estate)이 아니라 가짜 부동산(unreal estate)인 셈입니다!

서로 겹칠 수 있는 직사각형 구획들의 목록이 주어질 때, 이 구획들이 실제로 덮고 있는 전체 땅의 넓이를 구하세요. 겹치는 부분은 한 번만 셉니다.

입력

입력에는 여러 개의 테스트 케이스가 들어 있습니다. 각 테스트 케이스는 판매된 구획의 개수를 나타내는 정수 $n$ ( $0 < n \le 5000$ ) 이 적힌 줄로 시작합니다. 이어지는 $n$ 개의 줄에는 각각 하나의 직사각형 구획이 네 개의 실수로 주어집니다.

x1 y1 x2 y2

여기서 $(x_1, y_1)$ 은 남서쪽(왼쪽 아래) 꼭짓점, $(x_2, y_2)$ 는 북동쪽(오른쪽 위) 꼭짓점이며, $-1000 \le x_1 < x_2 \le 1000$ , $-1000 \le y_1 < y_2 \le 1000$ 을 만족합니다. 모든 구획의 넓이는 $1$ 이상입니다.

입력의 끝은 $0$ 하나만 적힌 줄로 표시됩니다.

출력

각 테스트 케이스마다, 모든 직사각형 구획이 덮는 실제 전체 넓이를 나타내는 실수 하나를 출력하세요. 이 값은 소수점 아래 정확히 두 자리까지 반올림하여 출력합니다. 공백은 출력하지 말고, 출력들 사이에 빈 줄도 넣지 마세요.

예제8

예제 1

입력

2
0 0 100 100
30 30 60 60
2
0 100 300 200
100 0 200 300
0

예상 출력

10000.00
50000.00

예제 2
입력
```
1
-10 -20 -5 -5
0
```
예상 출력
```
75.00
```
예제 3
입력
```
2
0 0 10 10
20 20 30 30
0
```
예상 출력
```
200.00
```

예제 4

입력

2
-1000 -1000 1000 1000
-500 -500 500 500
0

예상 출력

4000000.00

예제 5
입력
```
2
0 0 2.5 2.5
1.5 1.5 4 4
0
```
예상 출력
```
11.50
```
예제 6
입력
```
2
0 10 30 20
10 0 20 30
0
```
예상 출력
```
500.00
```

예제 7

입력

예상 출력

25.00
40.00

예제 8

입력

1
0 0 1 1
1
-1000 -1000 -999 0
0

예상 출력

1.00
1000.00