f003: 設置衛星通訊中心的城市
Tags :
Accepted rate : 11人/14人 ( 79% ) [非即時]
評分方式:
Strictly

最近更新 : 2020-04-26 20:34

Content

一個神奇的王國中,國王規定所有的道路都只能是東西向或是南北向,他認為這樣才能有整齊的城市。連帶的,所有的水管,電線,電話線,天然氣管線等等也都必須按照這個規則,只能有東西向跟南北向,要轉彎通通都是直角轉彎。

這個國家有許多城市,這些城市的市長會議決議要大家集資建設一個衛星通訊中心,期望能夠用最新的通訊科技與世界接軌。為了節省成本,衛星通訊中心必須建築在城市中。除了建設通訊中心的經費外,建設通訊中心與各個城市間的通訊線路也需要耗費相當多的金錢。因為通訊線路只能以東西向及南北向的方式架設,通訊中心到一個城市的通信線路長度,是彼此間東西向距離長度,加上南北向的距離長度。通往不同城市通訊線路不能夠共用,也就是說雖然通過同樣一個地方,目的地不同仍然要各自計算成本。而通訊線路的計價,與長度成正比,也就是說一條兩公里長的通訊線路是一條一公里長線路的兩倍價錢。所以選擇建築通訊中心的城市地點就格外重要,如果能夠挑到一個好地點,那麼就能夠花最少的金錢去建設到每個城市的獨立通訊線路。例如有四個城市 A、B、C、D,座標位置分布如下圖:

當通訊中心選擇建在 D 城市時:

通訊中心到城市 A 的通訊線路長度為 | 0–3 | + | 1–1 | = 3,

到城市 B 為 | 1–3 | + | 0–1 | = 3,

到城市 C 為 | 2–3 | + | 0–1 | = 2,

到城市 D 為 | 3–3 | + | 1–1 | = 0。

此時通訊線路的總長度為 3 + 3 + 2 + 0 = 8。

在這例子中,選擇將通訊中心建立在城市 B 或 C 均可使得通訊線路的總長度為最小 (最小值均為6)。所以將通訊中心建設在城市 B 或 C 時,能夠將建設費用降到最低。

請你寫一個程式來計算衛星通訊中心應該設置在哪裡,才能使得通訊線路的總長度為最小。

Input

輸入的第一列為一個整數 n (1 ≤ n ≤ 1000),代表有多少個城市。接下來有 n 列,每列有一對整數 xi 與 yi (0 ≤ xi,yi ≤ 500000),以空格分隔,代表第 i 個城市的平面座標是(xi,yi),即城市 i 坐落在離一個固定參考點以東 xi 公里,以北 yi公里的位置。

Output

第一列輸出設置城市的座標,X 座標跟 Y 座標之間用一個空格隔開,答案如有多組最佳解時,依X,Y座標的順序由小至大輸出設置城市的X與Y座標值。每個城市的座標值,各佔一列。接著的下一列,輸出通訊線路的最小總長度。每筆輸出資料之間以一空白列隔開。本題為嚴格比對(Strictly)評分方式,請務必按照說明進行輸出。

Sample Input #1
4
0 1
1 0
2 0
3 1
3
0 0
1 1
0 3
Sample Output #1
1 0
2 0
6

0 0
1 1
5

測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 1.0s , <1M
公開 測資點#1 (25%): 1.0s , <1M
公開 測資點#2 (25%): 1.0s , <1M
公開 測資點#3 (25%): 1.0s , <1K
Hint :

不准作弊!

改編自94學年度全國資訊學科能力競賽

Tags:
出處:
Caido2019學年度下學期延平中學國中組校內程式設計競賽 [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」