回『AP325』
d056: P-4-15. 最靠近的一對 (closest pair) (同 Q-5-5) (@@)
標籤 :
通過比率 : 85人/155人 ( 55% ) [非即時]
評分方式：
Tolerant

最近更新 : 2022-03-10 20:07

內容

平面兩點的 L1 距離為兩點的 $X$ 差值與 $Y$ 差值的和，也就說，如果兩點座標是 $(a,b)$ 與 $(c,d)$，則 L1 距離是 $|a-c|+|b-d|$。

輸入 $n$ 個點的座標，請計算出 L1 距離最近兩點的 L1 距離。

輸入說明

第一行為一個正整數 n，

接下來 n 行，每行兩個整數 x 與 y 代表一點的座標。

n 不超過 1e5，座標值絕對值不超過 1e8。

輸出說明

最近兩點的 L1距離。

範例輸入 #1 
4
-1 5
4 0
3 1
-2 -3
範例輸出 #1 
2
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <10M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (6%): 1.0s , <10M
公開 測資點#15 (6%): 1.0s , <1M
公開 測資點#16 (6%): 1.0s , <1M
公開 測資點#17 (6%): 1.0s , <1K
公開 測資點#18 (6%): 1.0s , <1K
提示 ：
標籤:
出處:
AP325 [管理者：
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」