시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB83443952.000%

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3
3 10 2
8 4 2
2 5 2

예제 출력 1

4

예제 입력 2

4
3 3 5
7 11 5
20 8 10
30 18 3

예제 출력 2

19

힌트

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

W3sicHJvYmxlbV9pZCI6IjI3OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5Y2NcdWIwYTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1ZDU3NCBcdWM1ZWNcdWI5ODRcdWM1ZDAgXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWQ1NjhcdWFlZDggXHViNzdkIFx1ZDM5OFx1YzJhNFx1ZDJmMFx1YmM4Y1x1YzVkMCBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4ODVcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1ZDJmMFx1Y2YxM1x1YjNjNCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMxXHVjODExIFx1YWQ2Y1x1YjllNFx1ZDU4OFx1YWNlMCwgXHVjNzc0XHVjODFjIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViYzMwXHViMmVjXHVkNTU4XHViN2VjIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NDAgXHVjNzc0XHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWMgXHVjNzA0XHVjNWQwXHViOWNjIFx1YzExYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjODg1XHVkNjAxXHVjNzc0XHVhYzAwIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjODhjXHVkNDVjXHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWM1ZWNcdWIzNWYgXHVhYzFjXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1ZDU1YyBcdWFjNzhcdWM3NGNcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YjMwMFx1YWMwMVx1YzEyMCk8XC9wPlxyXG5cclxuPHA+XHVjODg1XHVkNjAxXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjI5NCBcdWQyZjBcdWNmMTNcdWM3NDQgXHViYzFiXHVjNzNjXHViN2VjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHVjODcwXHVhZTA4IFx1YWM3OFx1YzViNCBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWNlNWNcdWFkNmNcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICh4LCB5KVx1Yzc3NFx1YmE3NCwgXHVjOWQxXHVjNWQwXHVjMTFjIFBcdWFjNzhcdWM3NGMgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWNmM1x1YWU0Y1x1YzljMCBcdWM4ODVcdWQ2MDFcdWM3NzRcdWI5N2MgXHViOWM4XHVjOTExXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQyZjBcdWNmMTNcdWM3NDQgXHViYWE4XHViNDUwIFx1YmMzMFx1YjJlY1x1ZDU1YyBcdWQ2YzRcdWM1ZDAgXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1YmMzMFx1YjJlY1x1ZDU1YyBcdWMyMWNcdWMxMWNcdWI5N2MgXHViMmU0XHVjMmRjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjODg1XHVkNjAxXHVjNzc0XHVhYzAwIFx1YWM3OFx1YzVjOFx1YjM1OCBcdWFjNzhcdWM3NGNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4ODVcdWQ2MDFcdWM3NzRcdWFjMDAgXHViYzMwXHViMmVjXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNThcdWM2NDAgXHViMDVkXHViOWM4XHVjZTVjIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDIwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4IHgsIHlcdWM2NDAgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgeCwgeSwgUCAmbGU7IDIwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQyZjBcdWNmMTNcdWM3NDQgXHViYzMwXHViMmVjXHVkNTVjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODg1XHVkNjAxXHVjNzc0XHVhYzAwIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWJjMzBcdWIyZWNcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YWM3OFx1Yzc0YyBcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YmMzMFx1YjJlY1x1Yzc0NCAoNCwgOClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0XHViYTc0LCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyAoNiwgNilcdWM3M2NcdWI4NWMgXHVhYzAwXHVjMTFjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjZTVjXHVhZDZjXHViOTdjIFx1YjljY1x1YjA5OFx1YWNlMCwgKDQsIDUpXHViODVjIFx1YWMwMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWI5Y2NcdWIwOThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc5NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNFVE5KQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgdGFraW5nIGFsbCBoaXMgZnJpZW5kcyB0byBhIFpheiBjb25jZXJ0IHNvb24gdG8gYmUgaGVsZCBpbiBaYWdyZWIuIEhlIGhhcyBhbHJlYWR5IG9idGFpbmVkIHRoZSB0aWNrZXRzLCBhbmQgaXMgbm93IHdhbGtpbmcgYXJvdW5kIHRoZSBuZWlnaGJvdXJob29kIGRlbGl2ZXJpbmcgdGhlbSB0byBldmVyeW9uZS48XC9wPlxyXG5cclxuPHA+TWlya28mIzM5O3MgbmVpZ2hib3VyaG9vZCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBDYXJ0ZXNpYW4gcGxhbmUuIFdoaWxlIHdhbGtpbmcsIE1pcmtvIGlzIHN0ZXBwaW5nIG9ubHkgb24gbGF0dGljZSAoaW50ZWdlci1jb29yZGluYXRlcykgcG9pbnRzIG9mIHRoYXQgcGxhbmUuIEhlIHRha2VzIGEgc2luZ2xlIHN0ZXAgdG8gbW92ZSB0byBhbnkgb25lIG9mIGVpZ2h0IGFkamFjZW50IGxhdHRpY2UgcG9pbnRzICh1cCwgZG93biwgbGVmdCwgcmlnaHQsIG9yIGRpYWdvbmFsbHkgaW4gYW55IGRpcmVjdGlvbikuPFwvcD5cclxuXHJcbjxwPkVhY2ggb25lIG9mIE1pcmtvJiMzOTtzIGZyaWVuZHMgYWxzbyBsaXZlcyBhdCBzb21lIGxhdHRpY2UgcG9pbnQgKHgsIHkpLCBhbmQgaXMgd2lsbGluZyB0byB3YWxrIHNvbWUgZGlzdGFuY2UgdG8gbWVldCBoaW0uIFNwZWNpZmljYWxseSwgTWlya28gd2lsbCBtZWV0IGEgZ2l2ZW4gZnJpZW5kIGF0IHNvbWUgbGF0dGljZSBwb2ludCB3aXRoIGRpc3RhbmNlIG9mIGF0IG1vc3QgUCBzdGVwcyBmcm9tIHRoaXMgZnJpZW5kJiMzOTtzIGhvdXNlLCB3aXRoIFAgZGVwZW5kaW5nIG9uIHRoZSBzcGVjaWZpYyBmcmllbmQmIzM5O3MgbGF6aW5lc3MuPFwvcD5cclxuXHJcbjxwPkFmdGVyIGZpbmlzaGluZyBoaXMgc3Ryb2xsLCBNaXJrbyBoYXMgcmVjYWxsZWQgdGhlIG9yZGVyIGluIHdoaWNoIGhlIGhhcyBtZXQgd2l0aCBoaXMgZnJpZW5kcy4gQ29tcHV0ZSB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2Ygc3RlcHMgdGhhdCBNaXJrbyBoYWQgdG8gbWFrZSBkdXJpbmcgaGlzIHN0cm9sbC4gTWlya28mIzM5O3Mgc3RhcnRpbmcgYW5kIGVuZGluZyBwb3NpdGlvbiBhcmUgbm90IGtub3duLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAyMDAgMDAwKSwgdGhlIG51bWJlciBvZiBNaXJrbyYjMzk7cyBmcmllbmRzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBkZXNjcmliaW5nIG9uZSBmcmllbmQ6IHgsIHksIGFuZCBQICgwICZsZTsgeCwgeSwgUCAmbGU7IDIwMCAwMDApLiBGcmllbmRzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggTWlya28gaGFzIG1ldCB0aGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIHN0ZXBzIHRoYXQgTWlya28gaGFkIHRvIG1ha2UuPFwvcD5cclxuIiwiaGludCI6IjxwPkZpcnN0IHNhbXBsZSBkZXNjcmlwdGlvbjogTWlya28gY291bGQgaGF2ZSBzdGFydGVkIGhpcyBzdHJvbGwgYXQgY29vcmRpbmF0ZXMgKDQsIDgpLCBtZXQgdGhlIGZpcnN0IGZyaWVuZCwgdGFrZW4gdHdvIHN0ZXBzIHRvIHRoZSBwb2ludCAoNiwgNiksIG1ldCB0aGUgc2Vjb25kIGZyaWVuZCwgdGFrZW4gdHdvIHN0ZXBzIHRvIHRoZSBwb2ludCAoNCwgNSkgYW5kIG1ldCB0aGUgdGhpcmQgZnJpZW5kIHRoZXJlLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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