981 . 曼哈頓距離
TopCoder
.jpg)
Tags
Description
平面上有 $n$ 個點 $P_1,P_2,\ldots,P_n$，其中 $P_i$ 的座標為 $(x_i,y_i)$。
對於平面上兩點 $(a,b),(c,d)$ 的曼哈頓距離為 $\mathrm{dist}((a,b),(c,d)) = |a-c|+|b-d|$。
對於每個 $k=2,3,\ldots,n$，請求出前 $k$ 個點兩兩曼哈頓距離總和，也就是 $$\sum_{i=1}^ k \sum_{j=1}^ {i-1} \mathrm{dist}(P_i,P_j).$$
Input Format
第一行輸入一個正整數 $n$。
接下來輸入 $n$ 行，其中第 $i$ 行輸入兩個整數 $x_i,y_i$，代表 $P_i$ 的座標。
- $2 \leq n\leq 2\times 10^ 5$
- $-10^ 8\le x_i, y_i\le 10^ 8$
Output Format
輸出 $n-1$ 行，第 $i$ 行輸出一個整數 $ans_{i+1}$，代表當 $k=i+1$ 時，問題的答案。
Sample Input 1
5 1 3 2 5 6 1 3 7 4 4
Sample Output 1
3 18 36 52
Hints
$ans_1=\mathrm{dist}(P_2,P_1) = |2-1|+|5-3| = 3$。
$ans_2=\mathrm{dist}(P_2,P_1)+\mathrm{dist}(P_3,P_1)+\mathrm{dist}(P_3,P_2) =$
$(|2-1|+|5-3|) + (|6-1|+|1-3|) + (|6-2|+|1-5|)= 3 + 7 + 8 = 18$。
Problem Source
YTP 2025 國中組程式挑戰營 p11
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 0~14 | $n\le 5000$ | 7 |
| 3 | 0~26 | 無額外限制 | 18 |