b582. 一個窩
標籤 :
通過比率 : 152人/207人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-09-30 15:30

內容

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) 的最小值。

範例輸入 #1
2
1
0 0
4
1 0 0 1 -1 0 0 -1
範例輸出 #1
0
4
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (60%): 1.0s , <1M
不公開 測資點#1 (30%): 1.5s , <50M
不公開 測資點#2 (10%): 1.5s , >50M
提示 :
標籤:
出處:
嘉義高中104資料學科能力競賽 [管理者: cthbst (吳宗達) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
34614 dfd8282@gmai ... (fishhh) b582
優化
163 2023-04-03 11:37