TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (58/58)

Submission's AC Ratio

79.0% (64/81)

Tags

Description

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

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

Output Format

第一行輸出設置城市的座標,X 座標跟 Y 座標之間用一個空格隔開。
第二行輸出通信線路總長度。
※若有多組解時,請輸出X座標最小的那組,若仍有多種可能,也請輸出Y座標最小者!

Sample Input 1

3
0 0
1 1
0 3

Sample Output 1

0 0
5

Sample Input 2

4
0 1
1 0
2 0
3 1

Sample Output 2

1 0
6

Hints

Problem Source

原TIOJ1147 / 94全國賽(prob 2)。

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4