TopCoder

Caido
Waimai

User's AC Ratio

84.2% (16/19)

Submission's AC Ratio

24.0% (24/100)

Tags

Description

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

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

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

起點也是格子點。兩點間的距離定義為 max(|x1x2||y1y2|)

Input Format

輸入第一行有一個正整數 n ( n100000 ),代表有幾個商店

接下來的 n 行每行有三個正整數 xi,yi,ti ( 1xi,yi5×108,1ti106)

代表第 i 個商店在 ( xi,yi ) ,有 ti 的需求量。

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