城市的街道都是長成平面直角座標系,這個城市中有 $n$ 個商店都在格子點上且有各自的需求量
你的任務是找出一個起點, 使得送完全部貨物所花費的距離最短
起點也是格子點。兩點間的距離定義為 $\max(|x_1-x_2|,|y_1-y_2|)$。
輸入第一行有一個正整數 $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$ 的需求量。
輸出兩個整數代表起點座標。(如果有多組答案輸出任一組皆可。)(如果有多組答案,輸出 $x$ 最小的一組 如果還是有多組解,請輸出 $y$ 最小的一組。)
(如果有多組答案請輸出最可能跟答案一樣的答案。)
如果有多組解,請輸出x最小的一組 如果還是有多組解,請輸出y最小的一組。 by poao899@2010/11/08
原TIOJ1293 / 雄中公假社'08 入退社考。(POI 05/06 Warehouse)。
Problem Provider:davidsu,Translate by:Tommy。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 20 |
2 | 1 | 20 |
3 | 2 | 20 |
4 | 3 | 20 |
5 | 4 | 20 |