d041: Q_3_13 X差值範圍內的最大Y差值
Tags : ch3
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-08-26 00:40

Content

 輸入平面上 $N$ 個點的座標 $(x_i,y_i)$ 以及一個正整數 $L$,計算並輸出任兩個 X 值相差不超過 $L$的點中,最大的 Y 差值

$\displaystyle\max_{1 \leq i \leq j \leq N} \{|y_i−y_j|∶|x_i−x_j|≤L \}$。
Time limit: 1秒


Input

第一行是 $N$ 與 $L$ ,第二行各點的 X 座標,第三行依序是對應點的 Y 座標,相鄰數字間以空白隔開。

$N \leq 2 \times 10^5$,座標絕對值不超過$10^9$。

Output

輸出所求的最大差值。

Sample Input #1
10 3
4 1 2 -10 3 5 6 9 7 8
6 1 4 10 3 9 8 1 5 7
Sample Output #1
7
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :

說明:X距離3以內的最大Y差值是(6,8)與(9,1),Y值差7。

Tags:
ch3
出處:
Dr.Wu [管理者:
ktlai@cmgsh.... (好冷阿)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」