Problem : 91 - Path

Problem Statistics

Solved Member: 5　　Submission: 17　　User Tried: 5

Statement:

TooDee 是一塊二維格子狀的土地（就像著名的笛卡爾坐標系那樣），在這裡生活著很多可愛的 Dee。
Dee 是像蜜蜂一樣的小動物，它們只在二維活動，而且它們非常的文明開化。
TooDee 的蜂窩和正常世界的蜂窩也是很不一樣的，它們是矩形的且它們的邊平行於TooDee 的地理坐標系，
就是說矩形的邊或者是東西走向，或者是南北走向。

因為Dees 是很高級的生物，它們有很多固定的飛行軌道，
這些軌道由一些平行於坐標軸的線段組成，線段只會在經緯度都是整數的點相交。
Dee 在 TooDee飛行時必須遵守以下規則（請記住TooDee 中所有點的經緯度都是整數）：

　※如果當前在點(XS, YS)，則下步只能飛到四個鄰點(XS, YS – 1), (XS, YS + 1),(XS – 1, YS ), (XS + 1, YS )
　※不可以進入蜂巢
　※只能在蜂巢的角或者邊上改變飛行方向
　※開始的時候可以向任何方向飛

今晚是公共財政大臣Deeficer 的女兒的生日，她想儘早回家，請幫她找到最快的回家路徑。
假設她每秒可以飛行一個單位的距離。

Input:Output:

每個測試點包含多組數據。
輸入的第一行包含一個整數T，表示測試數據的組數。
接下來依次描述這 T組數據，相鄰的兩組之間使用一個空行分隔。測試數據不多於 20 組。

對於每組數據，第一行包含4 個整數xs, ys, xt, yt，
表示Deeficer 的辦公室和家的坐標分別為(xs, ys)和(xt, yt)。
第二行包含一個整數n，表示蜂巢的個數。
接下來的n 行描述所有的蜂巢，其中第i 行包含4 個整數xi1, yi1, xi2, yi2，
表示第i 個蜂巢兩個對角的坐標分別為(xi1, yi1)和(xi2, yi2)。

任何兩個蜂巢都不會相交，也不會接觸（在角上也不會接觸）。
辦公室和家處在不同的位置。每個蜂巢的面積為正。

對於每一組數據，輸出一個整數，表示Deeficer 最快回家的時間（單位為秒），
如果她無法按規則回家，則輸出"No Path"（不含引號）。

Sample Input:Sample Output:

2

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

2 1 5 4
1
3 1 4 3

9
No Path

HINT:

對於20%的測試數據，n ≤ 10，所有的坐標都是小於100 的非負整數
對於60%的測試數據，n ≤ 100，所有坐標的絕對值都小於1000
對於100%的測試數據，1 ≤ n ≤ 1000，所有坐標的絕對值都是不超過$10^9$ 的整數

Source:

APIO 2011

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	10000ms	262144kb
1	10000ms	262144kb	5
2	10000ms	262144kb	5
3	10000ms	262144kb	5
4	10000ms	262144kb	5
5	10000ms	262144kb	5
6	10000ms	262144kb	5
7	10000ms	262144kb	5
8	10000ms	262144kb	5
9	10000ms	262144kb	5
10	10000ms	262144kb	5
11	10000ms	262144kb	5
12	10000ms	262144kb	5
13	10000ms	262144kb	5
14	10000ms	262144kb	5
15	10000ms	262144kb	5
16	10000ms	262144kb	5
17	10000ms	262144kb	5
18	10000ms	262144kb	5
19	10000ms	262144kb	5
20	10000ms	262144kb	5