2013年7月11日 星期四

11101 - Mall Mania

Problem B: Mall Mania

滑鐵盧有兩個大規模的購物商圈,每個商場被封閉在數個街區。Kim 和 Pat 喜歡在商圈裡到處逛逛,但不喜歡在商圈間走動,因為這樣沒辦法直接進行購物。他們想要知道最小的商圈間的距離,每個街區被街道和大道畫分成一個正方形,街道呈現東西向,大道呈現南北向,兩種都可以被標記為 0 到 2000 的整數編號 (西側的編號小,南側的編號小),可以假設街道將相當地窄,其寬度為 0。


每個商場有連續個完整的街區,這裡講的連續指的是街區都會藉由同一條邊相連。商圈不會有交集,且中間不會有空的區塊(空的區塊指不是商圈的區塊)。


輸入有多組測資, 每組有兩個商圈,每個商圈用 p (p ≥ 4) 的多邊形頂點表示,採用順時針的方式給點 (a,s),分別表示 avenue-street 的編號。

最後一組以 p = 0 結束程式。


對於每組測資,輸出一個連通兩個商圈的最短距離。
假設 Kim 和 Pat 只會沿著街道走。(即上下左右四個方位)

Sample Input

4
0 0 0 1 1 1 1 0
6
4 3 4 2 3 2
2 2 2 3
3 3
0

Output for Sample Input

2

Gordon V. Cormack