TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

42.9% (3/7)

Description

題目在這裡

在 Darkseer 的暗黑傳送完成之後 DarkKnight 也開始研發 Dark Teleport Field 法術。

這個法術可以在平地上建立魔法陣,使得魔法陣中的人可以在影響範圍內任意的瞬間移動(進入魔法陣並使用傳送算一步)。不過這不是免費的,每次使用都要支付一些法力;而且由於 DarkKnight 對魔法的認識,只能建立矩形的魔法陣,兩個魔法陣不能重疊;如圖,魔法陣的四邊也要和營地的四邊平行。
圖中是可能的移動方式。你的任務是幫 DarkKnight 計算兩點間的移動需要走多少步。

Input Format

輸入包含多組測試資料。 第一行有兩個整數,n (n≦50000) 表示營地的長度和寬度,m (m≦150) 表示有幾個魔法陣。
接下來有 m 行,每行有 4 個整數(X1i,Y1i,X2i,Y2i),表示魔法陣的左上角和右下角,座標範圍是 0~n-1。
接著有一個整數 t (t≦5),表示有 t 個問題,每個問題一行,五個整數,第一個是可以使用傳送的次數 k (k≦5),接下來 4 個數表示起點和終點的座標。

Output Format

對每個問題輸出從起點到終點需要幾步。

Sample Input

5 1
2 1 4 2
3
1 0 0 4 4
1 3 1 2 2
0 1 1 4 2

8 4
1 1 3 2
5 2 6 5
1 5 2 6
5 7 7 7
1
3 0 0 7 7

Sample Output

5
0
4
6

Hints

2015/8/1 將連結的內容搬到網頁上

Problem Source

原TIOJ1133 / [KSHSVC] 雄中公假社'07 公開賽。Problem Setter:DarkKnight。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1