-
大小: 1KB文件類型: .txt金幣: 1下載: 0 次發布日期: 2021-05-05
- 語言: 其他
- 標簽:
資源簡介
Description
問題描述:
在一個按照東西和南北方向劃分成規整街區的城市里,n個居民點散亂地分布在不同的街區中。用x 坐標表示東西向,用y坐標表示南北向。各居民點的位置可以由坐標(x,y)表示。街區中任意2 點(x1,y1)和(x2,y2)之間的距離可以用數值|x1-x2|+|y1-y2|度量。居民們希望在城市中選擇建立郵局的最佳位置,使n個居民點到郵局的距離總和最小。
編程任務:
給定n 個居民點的位置,編程計算n 個居民點到郵局的距離總和的最小值。
Input
輸入由多組測試數據組成。
每組測試數據輸入的第1 行是居民點數n,1≤n≤10000。接下來n 行是居民點的位置,每行2 個整數x 和y,-10000≤x,y≤10000。
Output
對應每組輸入,輸出的第1 行中的數是n 個居民點到郵局的距離總和的最小值。
Sample Input
5
1 2
2 2
1 3
3 -2
3 3
Sample Output
10
代碼片段和文件信息
評論
共有 條評論