DaDaSnake 住在一個名為 DaDaWorld 的世界,DaDaWorld 是一個棋盤格世界,就是所有位置都可以用整數座標 (x,y) 表示。還有一點就是因為 DaDaSnake 每次只能往上、下、左、右其中一個方向走一步,所以兩點之間的距離為曼哈頓距離,就是 P0(x0,y0) ,P1(x1,y1) 的距離為 |x0-x1|+|y0-y1|,記作 D(P0,P1)。
某 DaDaSnake 正在為自己找一個溫暖的窩,大家都知道 DaDaSnake 畢生的工作就是找餅乾,
所以牠希望到每個餅乾可能出現的地方的距離總合要最小,也就是告訴你餅乾出現的位置 P1(x1,y1),P2(x2,y2),...,Pn(xn,yn),找到一個 O(xo,yo),使 D(O,P1)+D(O,P2)+...+D(O,Pn) 最小,並輸出這個加總出來的值。
第一行會有一個正整數 T ,表示測試資料的數量。
對於每筆測試資料的第一行會有一個正整數 N(餅乾可能出現的位置的數量)。
以及 N 對數整數對(2N個整數),第 k 對整數 xk ,yk 表示第 k 個餅乾可能出的位置是(xk,yk)。
xk ,yk 可用 int 儲存
60% 測試資料中 1<= T <=10 , 1<= N <= 1000 ,所有座標的 y 座標皆相同。
30% 測試資料中 1<= T <=10 , 1<= N <= 100000
10% 測試資料中 1<= T <=5 , 1<= N <= 1000000
輸出 D(O,P1)+D(O,P2)+...+D(O,Pn) 的最小值。
2 1 0 0 4 1 0 0 1 -1 0 0 -1
0 4
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
34614 | dfd8282@gmai ... (fishhh) | b582 | 244 | 2023-04-03 11:37 |