b063. 2. 衛星通訊中心
標籤 :
通過比率 : 270人/304人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2007-12-08 23:50

內容

在一個神奇的王國中,國王規定所有的道路都只能是東西向或是南北向,他認為這樣才能有整齊的城市。連帶的,所有的水管,電線,電話線,天然氣管線等等也都必須按照這個規則,只能有東西向跟南北向,要轉彎通通都是直角轉彎。
這個國家有許多城市,這些城市的市長會議決議要大家集資建設一個衛星通訊中心,期望能夠用最新的通訊科技與世界接軌。為了節省成本,衛星通訊中心必須建築在城市中。除了建設通訊中心的經費外,建設通訊中心與各個城市間的通信線路也需要耗費相當多的金錢。因為通訊線路只能以東西向及南北向的方式架設,通訊中心到一個城市的通信線路長度,是彼此間東西向距離長度,加上南北向的距離長度。通往不同城市通信線路不能夠共用,也就是說雖然通過同樣一個地方,目的地不同仍然要各自計算成本。而通信線路的計價,與長度成正比,也就是說一條兩公里長的通信線路是一條一公里長線路的兩倍價錢。所以選擇建築通訊中心的城市地點就格外重要,如果能夠挑到一個好地點,那麼就能夠花最少的金錢去建設到每個城市的獨立通信線路。例如有四個城市 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 時,能夠將建設費用降到最低。
請你寫一個程式來計算衛星通訊中心應該設置在哪裡,才能使得通訊線路的總長度為最小。

 

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

第一行輸出設置城市的座標,X 座標跟 Y 座標之間用一個空格隔開,答案如有多組最佳解時,任意輸出一組最佳解。
第二行輸出通信線路總長度。

 

範例輸入 #1
3
0 0
1 1
0 3
4
0 1
1 0
2 0
3 1
範例輸出 #1
0 0
5
1 0
6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
提示 :
標籤:
出處:
94學年度全國資訊學科能力競賽

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
33972 yp11051026@y ... (911-24吳秉儒) b063
172 2023-02-20 17:27