在一個神奇的王國中,國王規定所有的道路都只能是東西向或是南北向,他認為這樣才能有整齊的城市。連帶的,所有的水管,電線,電話線,天然氣管線等等也都必須按照這個規則,只能有東西向跟南北向,要轉彎通通都是直角轉彎。
這個國家有許多城市,這些城市的市長會議決議要大家集資建設一個衛星通訊中心,期望能夠用最新的通訊科技與世界接軌。為了節省成本,衛星通訊中心必須建築在城市中。除了建設通訊中心的經費外,建設通訊中心與各個城市間的通信線路也需要耗費相當多的金錢。因為通訊線路只能以東西向及南北向的方式架設,通訊中心到一個城市的通信線路長度,是彼此間東西向距離長度,加上南北向的距離長度。通往不同城市通信線路不能夠共用,也就是說雖然通過同樣一個地方,目的地不同仍然要各自計算成本。而通信線路的計價,與長度成正比,也就是說一條兩公里長的通信線路是一條一公里長線路的兩倍價錢。所以選擇建築通訊中心的城市地點就格外重要,如果能夠挑到一個好地點,那麼就能夠花最少的金錢去建設到每個城市的獨立通信線路。例如有四個城市 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 時,能夠將建設費用降到最低。
請你寫一個程式來計算衛星通訊中心應該設置在哪裡,才能使得通訊線路的總長度為最小。
第一行輸出設置城市的座標,X 座標跟 Y 座標之間用一個空格隔開,答案如有多組最佳解時,任意輸出一組最佳解。
第二行輸出通信線路總長度。
3 0 0 1 1 0 3 4 0 1 1 0 2 0 3 1
0 0 5 1 0 6
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
33972 | yp11051026@y ... (911-24吳秉儒) | b063 | 258 | 2023-02-20 17:27 |