울타리 세우기

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

요약

다른 건물들의 금지 사각형 내부를 피하면서 저택의 사각형을 둘러싸는 축에 평행한 최소 길이의 울타리를 구하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 기하, 그래프, 최단 경로, 구현
정답자: 아직 제출이 없습니다

문제

레오폴트는 복권에 당첨되어 넓은 사유지를 얻었다. 앞으로 살게 될 본관 저택 외에도, 사유지에는 여러 건물이 있다. 부지에는 울타리가 없어서 레오폴트는 무단 침입을 막기 위해 울타리를 세우려 한다. 비용을 아끼기 위해, 울타리는 본관 저택만 둘러싸면 충분하다. 다만 한 가지 중요한 제약이 있다. 울타리는 어떤 건물에도 너무 가까이 있어서는 안 된다. 위에서 내려다보면 각 건물은 하나의 금지 직사각형 안에 들어 있으며, 울타리의 어떤 부분도 금지 직사각형의 내부에 놓일 수 없다. 모든 직사각형의 변은 x축과 y축에 평행하며, 울타리의 모든 부분도 x축 또는 y축에 평행해야 한다.

본관 저택을 둘러싸는, 규칙을 지키는 울타리의 최소 길이를 구하여라.

그림 1: 본관 저택(검은색)과 다른 세 건물, 그리고 각 건물의 금지 직사각형. 굵은 선은 본관 저택을 둘러싸는 최단 울타리 중 하나를 나타낸다.

입력

첫째 줄에 건물의 수를 나타내는 양의 정수 m (1 ≤ m ≤ 100)이 주어진다. 이어지는 m개의 줄에는 각 건물의 금지 직사각형이 하나씩 주어지며, 각 줄에는 네 개의 정수 tx, ty, bx, by가 공백으로 구분되어 주어진다. (tx, ty)는 직사각형의 왼쪽 위 꼭짓점, (bx, by)는 오른쪽 아래 꼭짓점의 좌표이다. 모든 좌표는 0 ≤ tx < bx ≤ 10000, 0 ≤ ty < by ≤ 10000을 만족한다. 첫 번째 직사각형이 본관 저택을 둘러싸는 금지 직사각형이다.

출력

본관 저택을 둘러싸는, 규칙을 지키는 울타리의 최소 길이를 나타내는 양의 정수 하나를 한 줄에 출력한다.

예제5

예제 1

입력

예상 출력

예제 2
입력
```
1
0 0 5 3
```
예상 출력
```
16
```
예제 3
입력
```
2
0 0 4 4
4 0 8 4
```
예상 출력
```
16
```
예제 4
입력
```
2
5 5 8 8
3 3 10 10
```
예상 출력
```
28
```
예제 5
입력
```
3
5 5 10 10
3 3 6 12
9 3 12 12
```
예상 출력
```
36
```