Problem : 200 - SETNJA

Problem Statistics

Solved Member: 3　　Submission: 6　　User Tried: 4

Problem：

Mirko 大大想要帶他的朋友們去一場將在 Zagreb 舉行的 "Zaz" 演唱會。他已經拿到足夠的票了，因此他現在正在他家附近散步，順便將票分給他的朋友們。

Mirko 家附近可以用一個笛卡爾坐標系來表示。當 Mirko 大大在走路的時候，他只會踩在格子點上〈即x, y座標均為整數〉。他走路時有八個方向，分別是上下左右和對角四方位。

Mirko 的每位朋友也都住在格子點上，並且他們會走到他們家附近和 Mirko 會面。Mirko 只能和朋友在格子點上會面，而且因為每個朋友都有屬於自己的懶惰程度 P，因此只能在離每位朋友家 P 步的距離碰面。

Mirko 回家之後，他記得他拜訪朋友們的順序，請你依照這個順序計算出他所需要走的步數最小值為多少。

請注意，Mirko 的起點和終點是未知的。

Input：

第一行有一個整數 N(2 ≤ N ≤ 200 000)，代表 Mirko 的朋友數量。

接下來有 N 行，每行有三個整數，分別代表這位朋友家的 x, y 座標和懶惰程度 P。

這N行資訊依照 Mirko 的拜訪順序排序。

Output：

請輸出唯一一行，代表 Mirko 完成他的任務所需要走的最少步數。

Sample Input：

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 Output：

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

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。

沒有留言:

張貼留言

歡迎留言或問問題～
若您的留言中包含程式碼，請參考這篇
如果留言不見了請別慌，那是因為被google誤判成垃圾留言，小莫會盡快將其手動還原

注意：只有此網誌的成員可以留言。

2016年2月25日 星期四

[HOJ 200][COI 2012]SETNJA (題目備份)

Problem : 200 - SETNJA

沒有留言:

張貼留言

2016年2月25日星期四