Setnja
레이팅 미적용의견: 0
\(7^{th}\) round (Croatian Olympiad in Informatics), April \(28^{th}\), 2012
Mirko is taking all his friends to a Zaz concert soon to be held in Zagreb. He has already obtained the
tickets, and is now walking around the neighbourhood delivering them to everyone.
Mirko's neighbourhood can be represented by a Cartesian plane. While walking, Mirko is stepping only
on lattice (integ\(er-co\)ordinates) points of that plane. He takes a single step to move to any one of
eight adjacent lattice points (up, down, left, right, or diagonally in any direction).
Each one of Mirko's friends also lives at some lattice point (x, y), and is willing to walk some distance
to meet him. Specifically, Mirko will meet a given friend at some lattice point with distance of at most
P steps from this friend's house, with P depending on the specific friend's laziness.
After finishing his stroll, Mirko has recalled the order in which he has met with his friends. Compute
the minimum possible number of steps that Mirko had to make during his stroll. Mirko's starting
and ending position are not known.
In test data worth a total of 30 points, all numbers in the input (including N) will be at most 200.
In test data worth an additional 30 points, no friend will have P greater than 10.
The first line of input contains the positive integer N (\(2 \le N \le 200\,000\)), the number of Mirko's
friends.
Each of the following N lines contains three integers describing one friend: x, y, and P (\(0 \le x\), y, P ≤
200 000). Friends are given in the order in which Mirko has met them.
The first and only line of output must contain the required minimum possible number of steps that
Mirko had to make.
3
3 10 2
8 4 2
2 5 244
3 3 5
7 11 5
20 8 10
30 18 319
First sample description: Mirko could have started his stroll at coordinates (4, 8), met the first friend,
taken two steps to the point (6, 6), met the second friend, taken two steps to the point (4, 5) and met
the third friend there.평가 및 의견
Setnja
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Setnja