問題描述:
小W是一個宅男,喜歡發呆,并幻想一些不切實際的事情。今天,小W又開始做他的白日夢了。他夢見他被困在了一條隧道里,周圍漆黑一片。作為一個宅男,小W自然地掏出了手機,打開定位系統,確定了他的位置。又由此在網上搜索到了關于隧道的信息。這條隧道是由一個點向外,呈六角螺旋形展開,并且沒有其他的支路。*小的一圈每條邊的長度都是1米,邊長向外依次增大到2,3…米,如下圖所示。
輸入數據以一個整數T<104開頭,表示測試數據組數。以下每行為一組測試數據,包括4個整數X1,Y1,X2,Y2,描述了小W所在的位置和出口位置的坐標。所有坐標的**值不超過1018,并保證答案不超出64位有符號整數的表示范圍。
輸出對于每組測試數據輸出一行,一個整數,表示小W所在的位置和出口的距離。
樣例輸入:
2
1 0 0 1
1 1 2 0
樣例輸出:
2
9
解題思路:
本題是一個典型的數學模擬題,如下圖所示(*好自己在題干圖的基礎上再多畫幾層,這有助于理解),我們可以觀察到每一圈的長度是一個公差為6的等差數列(7,13,19,25…),那么要計算兩個點之間的距離,其實只要知道它們在自己所屬那一圈行走的距離以及它們之間相差了幾圈即可,可以通過等差數列求和公式計算出相差圈數所代表的距離。
那么,我們可以把整個求解過程分為三步:
1.求出起點和終點分別位于哪一層,用getLayerOfPoint()這個函數來實現。
2.求出起點和終點在它們所在那一層上運動的距離,用getPointDisOfLayer()這個函數來實現。
3.根據等差數列求和公式、兩點之間相差的層數以及第2步中所計算出的距離來求解*后的結果。
特別需要注意的是:
1.本題中的起點并不一定位于終點的前面,即它們是可以反向的,所以我們在第3步之前若遇到起點位于終點之后的情況,應該交換它們兩個的位置。
2.本題計算距離需要求**值,但abs()函數無法求解long long型的**值,需要自己實現一個求解**值的方法。
代碼實現:
總結:
這題*開始做的時候,踩了很多的坑。在某些地方不小心使用了int型導致數值小的用例可以通過,程序邏輯沒問題,但是一直WA。后來試了很多較大的數據,發現是沒有使用long long型變量。同時,判斷點位于哪個象限時,應該對x與y分別進行判斷,而不是使用乘法判斷,乘法可能會導致計算結果超出long long所能表示的范圍。*好的辦法還是自己多畫一下這個圖,對過程自然而然就清楚了。