도로

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

요약

N개의 축 정렬 직사각형의 변을 따라 A에서 B까지 가는 최단 경로의 길이를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 기하, 정렬
정답자: 아직 제출이 없습니다

문제

한 섬이 $N$ 개의 땅으로 나뉘어 있으며, 각 땅은 좌표축에 평행한 직사각형 모양입니다. 점 $A$ 에서 점 $B$ 까지 도로를 건설하려고 합니다. 어떤 땅 주인도 자신의 땅이 도로 때문에 여러 조각으로 쪼개지는 것을 원하지 않으므로, 도로는 반드시 땅들의 경계(직사각형의 변)를 따라서만 지나가야 합니다.

점 $A$ 에서 점 $B$ 까지 이르는 가장 짧은 도로의 길이를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 땅의 개수 $N$ ( $1 \le N \le 1000$ )이 주어집니다. 이어지는 $N$ 개의 줄에는 각 땅을 나타내는 직사각형의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표 $X_0$ , $Y_0$ , $X_1$ , $Y_1$ 이 주어집니다. 다음 줄에는 점 $A$ 의 좌표 $X_A$ , $Y_A$ 가, 마지막 줄에는 점 $B$ 의 좌표 $X_B$ , $Y_B$ 가 주어집니다.

모든 좌표는 $1\,000\,000$ 이하의 음이 아닌 정수입니다. 점 $A$ 와 점 $B$ 는 항상 어떤 땅의 경계 위에 있습니다. 또한 모든 땅은 하나의 섬을 이루며(섬 안에 호수가 있을 수도 있습니다), $A$ 에서 $B$ 로 가는 도로가 항상 존재함이 보장됩니다.

출력

점 $A$ 에서 점 $B$ 까지 이르는 가장 짧은 도로의 길이 $L$ 을 정수 하나로 출력합니다. 모든 좌표가 정수이고 도로는 좌표축에 평행한 선분만을 따라가므로 $L$ 은 항상 정수입니다.

예제3

예제 1
입력
```
3
4 1 7 4
3 4 6 5
1 3 4 4
4 5
3 3
```
예상 출력
```
5
```
예제 2
입력
```
1
0 0 2 2
0 0
2 0
```
예상 출력
```
2
```
예제 3
입력
```
1
0 0 3 4
0 0
3 4
```
예상 출력
```
7
```