TopCoder

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

User's AC Ratio

83.3% (15/18)

Submission's AC Ratio

23.2% (23/99)

Tags

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 \times 10^ 8, 1\leq t_i \leq 10^ 6$)

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

Output Format

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

Sample Input 1

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

Sample Output 1

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

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