시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 4 4 30.769%

문제

올해 여름에 종혁이는 친구들과 함께 락 페스티벌에 가려고 한다. 종혁이는 친구들의 티켓도 자신이 직접 구매했고, 이제 티켓을 친구들에게 배달하러 가려고 한다.

종혁이와 친구들이 살고 있는 마을은 이차원 평면으로 나타낼 수 있다. 종혁이는 정수 좌표 위에만 서 있을 수 있다. 종혁이가 현재 있는 좌표에서 인접한 여덟 개의 좌표 중 하나로 한 걸음에 이동할 수 있다. (위, 아래, 왼쪽, 오른쪽, 대각선)

종혁이의 친구는 티켓을 받으러 자신의 집에서 조금 걸어 나올 수 있다. 즉, 친구가 살고 있는 집의 좌표가 (x, y)이면, 집에서 P걸음 떨어진 곳까지 종혁이를 마중나올 수 있다. P는 각각의 친구에 따라서 다르다.

티켓을 모두 배달한 후에 종혁이는 배달한 순서를 다시 생각해 보았다. 이 때, 종혁이가 걸었던 걸음의 최소값을 구하는 프로그램을 작성하시오. 종혁이가 배달을 시작한 위치와 끝마친 위치의 좌표는 알 수 없다.

입력

첫째 줄에 친구의 수 N이 주어진다. (2 ≤ N ≤ 200,000)

다음 N개 줄에는 집의 위치 x, y와 P가 주어진다. (0 ≤ x, y, P ≤ 200,000)

종혁이가 티켓을 배달한 순서대로 입력이 주어진다.

출력

첫째 줄에 종혁이가 티켓을 배달하는데 필요한 걸음 수의 최소값을 출력한다.

예제 입력

3
3 10 2
8 4 2
2 5 2

예제 출력

4

힌트

배달을 (4, 8)에서 시작한다면, 첫 번째 친구를 만날 수 있다. 그 다음 (6, 6)으로 가서 두 번째 친구를 만나고, (4, 5)로 가서 세 번째 친구를 만나면 된다.

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Croatian Olympiad in Informatics 2012 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: khsoo01