TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

25.0% (5/20)

Description

城市的街道都是長成平面直角座標系,這個城市中有 n 個商店都在格子點上且有各自的需求量

你的任務是找出一個起點, 使得送完全部貨物所花費的距離最短

起點到每個商店只能每次送一單位的需求,每送完一單位的需求就必須回到起點

起點也是格子點。兩點間的距離定義為 Max$(|x_1-x_2|,|y_1-y_2|)$。

Input Format

輸入第一行有一個正整數$n$ ( $n\leq 100000$ ),代表有幾個商店

接下來的 $n$ 行每行有三個正整數 $x_i, y_i, t_i$ ( $1\leq x_i, y_i \leq 5*108, 1\leq t_i \leq 106$)

代表第 $i$ 個商店在 ( $x_i, y_i$ ) ,有 $t_i$ 的需求量。

Output Format

輸出兩個整數代表起點座標。(如果有多組答案輸出任一組皆可。)(如果有多組答案,輸出x最小的一組 如果還是有多組解,請輸出y最小的一組。)

Sample Input

3
2 2 1
6 2 1
4 6 1
3
2 2 1
6 2 1
4 6 1

Sample Output

4 4
4 4

Hints

(如果有多組答案請輸出最可能跟答案一樣的答案。)

如果有多組解,請輸出x最小的一組 如果還是有多組解,請輸出y最小的一組。 by poao899@2010/11/08

Problem Source

原TIOJ1293 / 雄中公假社'08 入退社考。(POI 05/06 Warehouse)。
Problem Provider:davidsu,Translate by:Tommy。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536
2 5000 65536 65536
3 5000 65536 65536
4 5000 65536 65536