題目描述

嘉城是一座長方形的幸福城市，道路四通八達，而且都與嘉城的邊界平行或垂直，任意兩條相鄰且平行的道路，或者邊界與最近的平行道路的間距都恰為 1 單位距離。因為這樣的特性，我們用二維平面來描述嘉城的任意路口：坐標平面上x軸向東側為正、y軸向北側為正，並將達嘉城南側端點之坐標位置定為(x1,y1)，東北側端點之坐標位置定為 (x2,y2)，也就是說在坐標點 (x,y) 時，向東側走 1 單位距離，會到達 (x+1,y)；向北側走 1 單位距離， 則會到達(x,y+1)。

嘉城的交通非常便利：每當走到四周的邊界，就會被傳送至與該邊界平行之另一側邊界之對應位置。舉例來說，若走到北側邊界 (x,y2) 上，會被傳送到 (x,y1)的位置；若走到 南側邊界 (x,y1) 上，會被傳送到 (x,y2) 的位置。類似地，若走到東側邊界 (x2,y) 上，會被傳送到 (x1,y) 的位置；走到西側邊界(x1,y) 上，會被傳送 (x2,y) 的位置。

現有兩個人身在嘉城的不同路口，想要約在一個不在邊界上的路口會合，並且希望兩人所行走的距離總和愈短最好。兩人經過一番思考，驚覺這正是傳說中的最短路徑問題！於是已經學過最短路徑演算法的你，自告奮勇想幫忙他們計算這個問題。

輸入格式

第一列輸入這城市的西南側端點之座標，格式為x1 y1，數值之間用空格分隔

第二列輸入這城市的東北側端點之座標，格式為x2 y2，數值之間用空格分隔

第三列輸入第一個人所站的座標，格式為x3 y3，數值之間用空格分隔

第四列輸入第二個人所站的座標，格式為x4 y4，數值之間用空格分隔

以上輸入的數值全為整數

輸出格式

輸出一個正整數，表示這兩個人所行走的最小距離總和。

Samples

["0 0\r\n10 10\r\n5 5\r\n6 7","-2 -3\r\n2 3\r\n-1 -2\r\n1 2","-5 -6\r\n0 0\r\n-4 -4\r\n-2 0"]

["3","4","4"]

原始資料

• Zero1 題號：a248
• Hydro 題號：Z0248
• Locale：zh_TW
• Display：open