回分類題庫
g037: F.數格子點
關鍵字: NPSC 2007 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 95 Times / 90 Users | Submit : 130 Times / 92 Users | Accepted rate : 98%
題目加入時間 : 2011-12-16 15:11

Content: 简体中文

小明正在做一道數學難題,百思不得其解,碰巧小華來拜訪,便向小華說明了問題,看能不能透過討論得到一點頭緒。

小明:「這題目是問X-Y座標系上兩個格子點的連線會通過幾個格子點,就像這張圖一樣,起點是(1, 2),終點是(13, 8)。」

小華:「呃!什麼是格子點呢?以前沒聽過耶。」
小明:「格子點是指X和Y值都是整數的點,這條連線會依序通過(1, 2)、(3, 3)、(5, 4)、(7, 5)、(9, 6)、(11, 7),最後連到(13, 8)。」
小華:「你是怎麼找到這些點呢?」
小明:「我把線畫在方格紙上,再將線段和格子的交點找出來,就像這張圖一樣。但這方法太笨了,很累人。」

 

小華:「我好像發現一件奇怪的事,這些格子點剛好把兩個點X值的差距(13 – 1 = 12)等分成6份。」
小明:「對耶!而且Y值也有類似的情況,但這有什麼用處呢?」

Input:

第一行整數n ( 1 ≦ n ≦ 20) 說明測試檔案有幾組測試資料,接著 n 組測試資料,每組四個整數,依序為起點的X值、起點的Y值、終點的X值、終點的Y值。所有的X、Y值都是介於正負一百之間的整數。

Output:

每組測資輸出一行數字,表示起點和終點的連線通過多少格子點。輸出一共 n 行。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2 
1 2 13 8
-1 4 -1 3

Sample Output :

7
2

Hint :

Author :

NPSC 2007 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum