Description

LHX教主最近總困擾于前來膜拜他的人太多了，所以他給他的花園加上了一道屏障。?

?

可以把教主的花園附近區域抽像成一個正方形網格組成的網絡，每個網格都對應了一個坐標（均為整數，有可能為負），若兩個網格(x1, y1)，(x2, y2)有|x1 � x2| + |y1 � y2| = 1，則說這兩個網格是相鄰的，否則不是相鄰的。?
教主在y = 0處整條直線上的網格設置了一道屏障，即所有坐標為(x, 0)的網格。當然，他還要解決他自己與內部人員的進出問題，這樣教主設置了N個入口a1, a2, …, aN可供進出，即對于y = 0上的所有網格，只有 (a1, 0)，(a2, 0)， ……， (aN, 0) 可以通過，之外的所有縱坐標為0的網格均不能通過，而對于(x, y)有y不為0的網格可以認為是隨意通過的。?
現在教主想知道，給定M個點對(x1, y1)，(x2, y2)，并且這些點均不在屏障上，詢問從一個點走到另一個點最短距離是多少，每次只能從一個格子走到相鄰的格子。?

Input

輸入的第1行為一個正整數N，為屏障上入口的個數。?
第2行有N個整數，a1, a2, …, aN，之間用空格隔開，為這N個入口的橫坐標。?
第3行為一個正整數M，表示了M個詢問。?
接下來M行，每行4個整數x1, y1, x2, y2，有y1與y2均不等于0，表示了一個詢問從(x1, y1)到(x2, y2)的最短路。?

Output

輸出共包含m行，第i行對于第i個詢問輸出從(x1, y1)到(x2, y2)的最短路距離是多少。 2
2 -1
2
0 1 0 -1
1 1 2 2

?

4
2

1 var
2 a:array[1..100000] of int64;
3 i,b:longint;
4 x1,y1,x2,y2,f,n,s,t,tmp,ans,m:int64;
5 k:double;
6 ?procedure qs(s,t:longint);
7 ?var
8 i,j,x:longint;
9 ?begin
10 i:=s;
11 j:=t;
12 x:=a[i];
13 repeat
14 while (i<j) and (x<=a[j]) do dec(j);
15 if i<j then
16 begin
17 a[i]:=a[j];
18 inc(i);
19 end;
20 while (i<J) and (x>=a[i]) do inc(i);
21 if i<j then
22 begin
23 a[j]:=a[i];
24 dec(j);
25 end;
26 until i=j;
27 a[i]:=x;
28 inc(i);
29 dec(j);
30 if s<j then qs(s,j);
31 if i<T then qs(i,t);
32 end;
33 begin
34 readln(n);
35 for i:=1 to n do
36 read(a[i]);
37 qs(1,n);
38 readln(m);
39 for b:=1 to m do
40 begin
41 readln(x1,y1,x2,y2);
42 if y1*y2>0 then
43 writeln(abs(y2-y1)+abs(x2-x1))
44 else
45 begin
46 if x1=x2 then k:=x1
47 else
48 begin
49 k:=(y2-y1)/(x2-x1);
50 k:=x1-y1/k;
51 end;
52 s:=1;
53 t:=n;
54 while s<t do
55 begin
56 tmp:=(s+t+1) div 2;
57 if a[tmp]<k then s:=tmp
58 else t:=tmp-1;
59 end;
60 ans:=maxlongint;
61 if s=1 then inc(s);
62 for i:=s-1 to n do
63 begin
64 tmp:=abs(x1-a[i])+abs(y1)+abs(x2-a[i])+abs(y2);
65 if tmp<ans then ans:=tmp else break;
66 end;
67 writeln(ans);
68 end;
69 end;
70 end.

?

轉載于:https://www.cnblogs.com/PisntD/archive/2010/11/17/1879768.html

總結

以上是生活随笔為你收集整理的Garden的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。