Submit Ranklist
Problem : 200 - SETNJA
Problem Statistics
Solved Member:
3 Submission:
6 User Tried:
4 Statement:
Mirko 大大想要帶他的朋友們去一場將在 Zagreb 舉行的 "Zaz" 演唱會。他已經拿到足夠的票了,因此他現在正在他家附近散步,順便將票分給他的朋友們。
Mirko 家附近可以用一個笛卡爾坐標系來表示。當 Mirko 大大在走路的時候,他只會踩在格子點上〈即x, y座標均為整數〉。他走路時有八個方向,分別是上下左右和對角四方位。
Mirko 的每位朋友也都住在格子點上,並且他們會走到他們家附近和 Mirko 會面。Mirko 只能和朋友在格子點上會面,而且因為每個朋友都有屬於自己的懶惰程度 P,因此只能在離每位朋友家 P 步的距離碰面。
Mirko 回家之後,他記得他拜訪朋友們的順序,請你依照這個順序計算出他所需要走的步數最小值為多少。
請注意,Mirko 的起點和終點是未知的。
Input:Output:
第一行有一個整數 N(2 ≤ N ≤ 200 000),代表 Mirko 的朋友數量。
接下來有 N 行,每行有三個整數,分別代表這位朋友家的 x, y 座標和懶惰程度 P。
這N行資訊依照 Mirko 的拜訪順序排序。
請輸出唯一一行,代表 Mirko 完成他的任務所需要走的最少步數。
Sample Input:Sample Output:
SAMPLE A:
3
3 10 2
8 4 2
2 5 2
SAMPLE B:
4
3 3 5
7 11 5
20 8 10
30 18 3
SAMPLE A:
4
SAMPLE B:
19
HINT:
占分 30% 的測資裡,N 最大值為 200。
另外 30% 的測資,P 不會超過 10。
第一筆範例測資中,Mirko 從 (4, 8) 碰到他的第一個朋友,並在 (6, 6) 碰到第二個朋友,並在 (4, 5) 碰到他的第三個朋友。
Source:
COI 2012
Problem Setter
Nekosyndrome Testdata:
Test | Time | Memory | Score |
---|
0-1 | 3000ms | 262144kb | |
0-2 | 3000ms | 262144kb | |
1 | 3000ms | 262144kb | 10 |
2 | 3000ms | 262144kb | 10 |
3 | 3000ms | 262144kb | 10 |
4 | 3000ms | 262144kb | 10 |
5 | 3000ms | 262144kb | 10 |
6 | 3000ms | 262144kb | 10 |
7 | 3000ms | 262144kb | 10 |
8 | 3000ms | 262144kb | 10 |
9 | 3000ms | 262144kb | 10 |
10 | 3000ms | 262144kb | 10 |