UVA-10642 - Can You Solve It?

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20110927 大學程式能力檢定 CPE」題目。
• 相同題目：NCTU-23821

題意概要

請參考下圖的二維座標系統 (笛卡兒座標系)，垂直為 $X$ 軸，水平為 $Y$ 軸，每個圓點有一個座標。在座標系統上可以隨著箭頭所表示之路徑，從座標上的一圓點出發移動到另一圓點，所經過之路徑的距離定義為：經過的座標點數加 $1$，例如從 $(0, 3)$ 到 $(3, 0)$ 必須先經過 $(1, 2)$ 與 $(2, 1)$ 兩點，所以距離等於 $2 + 1 = 3$ 。本題會給定兩個座標點，請你計算從出發點到目的點的距離，你可以假設不能用箭頭的反方向回頭。

• 分析：簡單來說，本題要找出兩點需要經過多少點可以到達，點到點走的方式請參考原題目的圖。因此，可以先計算出 $(0, 0)$ 到第一個點的距離 ($s_1$)，在計算 $(0, 0)$ 到第二點的距離 ($s_2$)，而 $s_2 - s_1$ 即是答案。

Input

The first line in the input is the number of test cases $n$ ($0 < n \le 500$) to handle. Following there are n lines each containing four integers ($0 \le each_integer \le 100,000$) the first pair of which represents the coordinates of the source circle and the other represents that of the destination circle. The coordinates are listed in a form $(x, y)$.

Output

For each pair of integers your program should output the case number first and then the number of step(s) to reach the destination from the source. You may assume that it is always possible to reach the destination circle from the source circle.

Sample Input

3
0 0 0 1
0 0 1 0
0 0 0 2

Sample Output

Case 1: 1
Case 2: 2
Case 3: 3