1133 . Dark Teleport Field
TopCoder
Tags
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 1
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
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 1
5
0
4
6
0
4
6
Hints
2015/8/1 將連結的內容搬到網頁上
Problem Source
原TIOJ1133 / [KSHSVC] 雄中公假社'07 公開賽。Problem Setter：DarkKnight。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |