확장된 맨해튼 거리

맨해튼의 거리는 격자를 이룬다. 격자선이 x축과 y축에 평행할 때, 건물을 가로지르지 않고 거리(도로)를 따라서만 한 지점에서 다른 지점으로 이동하는 거리는 $\Delta x + \Delta y$ 와 같다. 이를 맨해튼 거리라고 한다.

이제 도시 격자 바깥의 땅은 완전히 평평하고 아무런 장애물이 없어서 어느 방향으로든 자유롭게 이동할 수 있다고 하자. 우리는 점 $A$ 에서 점 $B$ 로 이동하려 하며, 각 점은 격자 안, 격자 위, 또는 격자 바깥에 있을 수 있다. 도시 바깥에서 두 점 사이의 최단 거리가 반드시 맨해튼 거리인 것은 아니다. 두 점이 모두 격자 위에 있으면 맨해튼 거리이지만, 예를 들어 두 점이 모두 격자의 북쪽에 있으면 최단 거리는 직선(유클리드) 거리이다. 그 밖의 경우는 더 복잡할 수 있다.

도시 격자의 마주 보는 두 꼭짓점이 주어진다. 격자선은 좌표축에 평행하며, 인접한 격자선(가로 또는 세로) 사이의 간격은 $1$ 단위이다. 정수 좌표를 갖는 두 점 $A$ 와 $B$ 도 주어진다. 도시 격자 안에서는 격자선(도로)을 따라서만 이동할 수 있다는 조건 아래, $A$ 에서 $B$ 까지의 최단 경로의 길이를 구하는 프로그램을 작성하라.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋은 여덟 개의 정수가 있는 한 줄이다.

$$x_L \quad y_L \quad x_U \quad y_U \quad x_A \quad y_A \quad x_B \quad y_B$$

여기서 $L = (x_L, y_L)$ 와 $U = (x_U, y_U)$ 는 각각 도시 격자의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점이고, $A = (x_A, y_A)$ 와 $B = (x_B, y_B)$ 는 이동하려는 두 점이다.

모든 정수는 $-1000$ 이상 $1000$ 이하이며, $x_L < x_U$ 이고 $y_L < y_U$ 이다. 입력은 여덟 개의 $0$ 으로 이루어진 줄로 끝나며, 이 줄은 처리하지 않는다.

각 데이터셋에 대해, $A$ 에서 $B$ 까지의 최단 경로의 길이를 소수점 아래 셋째 자리까지 반올림하여 한 줄에 출력한다.