시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 30 11 9 33.333%

문제

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

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

종혁이의 친구는 티켓을 받으러 자신의 집에서 조금 걸어 나올 수 있다. 즉, 친구가 살고 있는 집의 좌표가 (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

힌트

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

W3sicHJvYmxlbV9pZCI6IjI3OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5Y2NcdWIwYTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1ZDU3NCBcdWM1ZWNcdWI5ODRcdWM1ZDAgXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWQ1NjhcdWFlZDggXHViNzdkIFx1ZDM5OFx1YzJhNFx1ZDJmMFx1YmM4Y1x1YzVkMCBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM4ODVcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1ZDJmMFx1Y2YxM1x1YjNjNCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMxXHVjODExIFx1YWQ2Y1x1YjllNFx1ZDU4OFx1YWNlMCwgXHVjNzc0XHVjODFjIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViYzMwXHViMmVjXHVkNTU4XHViN2VjIFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YzY0MCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NDAgXHVjNzc0XHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWMgXHVjNzA0XHVjNWQwXHViOWNjIFx1YzExYyBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjODg1XHVkNjAxXHVjNzc0XHVhYzAwIFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjODhjXHVkNDVjXHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWM1ZWNcdWIzNWYgXHVhYzFjXHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1ZDU1YyBcdWFjNzhcdWM3NGNcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YjMwMFx1YWMwMVx1YzEyMCk8XC9wPlxyXG5cclxuPHA+XHVjODg1XHVkNjAxXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjI5NCBcdWQyZjBcdWNmMTNcdWM3NDQgXHViYzFiXHVjNzNjXHViN2VjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM5ZDFcdWM1ZDBcdWMxMWMgXHVjODcwXHVhZTA4IFx1YWM3OFx1YzViNCBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWNlNWNcdWFkNmNcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwICh4LCB5KVx1Yzc3NFx1YmE3NCwgXHVjOWQxXHVjNWQwXHVjMTFjIFBcdWFjNzhcdWM3NGMgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWNmM1x1YWU0Y1x1YzljMCBcdWM4ODVcdWQ2MDFcdWM3NzRcdWI5N2MgXHViOWM4XHVjOTExXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQyZjBcdWNmMTNcdWM3NDQgXHViYWE4XHViNDUwIFx1YmMzMFx1YjJlY1x1ZDU1YyBcdWQ2YzRcdWM1ZDAgXHVjODg1XHVkNjAxXHVjNzc0XHViMjk0IFx1YmMzMFx1YjJlY1x1ZDU1YyBcdWMyMWNcdWMxMWNcdWI5N2MgXHViMmU0XHVjMmRjIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWFjNzhcdWM1YzhcdWIzNTggXHVhYzc4XHVjNzRjXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjODg1XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjA1ZFx1YjljOFx1Y2U1YyBcdWM3MDRcdWNlNThcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNlNWNcdWFkNmNcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OCB4LCB5XHVjNjQwIFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHgsIHksIFAgJmxlOyAyMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWM4ODVcdWQ2MDFcdWM3NzRcdWFjMDAgXHVkMmYwXHVjZjEzXHVjNzQ0IFx1YmMzMFx1YjJlY1x1ZDU1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzg4NVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQyZjBcdWNmMTNcdWM3NDQgXHViYzMwXHViMmVjXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjNzhcdWM3NGMgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YmMzMFx1YjJlY1x1Yzc0NCAoNCwgOClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0XHViYTc0LCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyAoNiwgNilcdWM3M2NcdWI4NWMgXHVhYzAwXHVjMTFjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjZTVjXHVhZDZjXHViOTdjIFx1YjljY1x1YjA5OFx1YWNlMCwgKDQsIDUpXHViODVjIFx1YWMwMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWI5Y2NcdWIwOThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc5NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNFVE5KQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgdGFraW5nIGFsbCBoaXMgZnJpZW5kcyB0byBhIFpheiBjb25jZXJ0IHNvb24gdG8gYmUgaGVsZCBpbiBaYWdyZWIuIEhlIGhhcyBhbHJlYWR5IG9idGFpbmVkIHRoZSB0aWNrZXRzLCBhbmQgaXMgbm93IHdhbGtpbmcgYXJvdW5kIHRoZSBuZWlnaGJvdXJob29kIGRlbGl2ZXJpbmcgdGhlbSB0byBldmVyeW9uZS48XC9wPlxyXG5cclxuPHA+TWlya28mIzM5O3MgbmVpZ2hib3VyaG9vZCBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBDYXJ0ZXNpYW4gcGxhbmUuIFdoaWxlIHdhbGtpbmcsIE1pcmtvIGlzIHN0ZXBwaW5nIG9ubHkgb24gbGF0dGljZSAoaW50ZWdlci1jb29yZGluYXRlcykgcG9pbnRzIG9mIHRoYXQgcGxhbmUuIEhlIHRha2VzIGEgc2luZ2xlIHN0ZXAgdG8gbW92ZSB0byBhbnkgb25lIG9mIGVpZ2h0IGFkamFjZW50IGxhdHRpY2UgcG9pbnRzICh1cCwgZG93biwgbGVmdCwgcmlnaHQsIG9yIGRpYWdvbmFsbHkgaW4gYW55IGRpcmVjdGlvbikuPFwvcD5cclxuXHJcbjxwPkVhY2ggb25lIG9mIE1pcmtvJiMzOTtzIGZyaWVuZHMgYWxzbyBsaXZlcyBhdCBzb21lIGxhdHRpY2UgcG9pbnQgKHgsIHkpLCBhbmQgaXMgd2lsbGluZyB0byB3YWxrIHNvbWUgZGlzdGFuY2UgdG8gbWVldCBoaW0uIFNwZWNpZmljYWxseSwgTWlya28gd2lsbCBtZWV0IGEgZ2l2ZW4gZnJpZW5kIGF0IHNvbWUgbGF0dGljZSBwb2ludCB3aXRoIGRpc3RhbmNlIG9mIGF0IG1vc3QgUCBzdGVwcyBmcm9tIHRoaXMgZnJpZW5kJiMzOTtzIGhvdXNlLCB3aXRoIFAgZGVwZW5kaW5nIG9uIHRoZSBzcGVjaWZpYyBmcmllbmQmIzM5O3MgbGF6aW5lc3MuPFwvcD5cclxuXHJcbjxwPkFmdGVyIGZpbmlzaGluZyBoaXMgc3Ryb2xsLCBNaXJrbyBoYXMgcmVjYWxsZWQgdGhlIG9yZGVyIGluIHdoaWNoIGhlIGhhcyBtZXQgd2l0aCBoaXMgZnJpZW5kcy4gQ29tcHV0ZSB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2Ygc3RlcHMgdGhhdCBNaXJrbyBoYWQgdG8gbWFrZSBkdXJpbmcgaGlzIHN0cm9sbC4gTWlya28mIzM5O3Mgc3RhcnRpbmcgYW5kIGVuZGluZyBwb3NpdGlvbiBhcmUgbm90IGtub3duLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAyMDAgMDAwKSwgdGhlIG51bWJlciBvZiBNaXJrbyYjMzk7cyBmcmllbmRzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0aHJlZSBpbnRlZ2VycyBkZXNjcmliaW5nIG9uZSBmcmllbmQ6IHgsIHksIGFuZCBQICgwICZsZTsgeCwgeSwgUCAmbGU7IDIwMCAwMDApLiBGcmllbmRzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggTWlya28gaGFzIG1ldCB0aGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIHN0ZXBzIHRoYXQgTWlya28gaGFkIHRvIG1ha2UuPFwvcD5cclxuIiwiaGludCI6IjxwPk1pcmtvIGNvdWxkIGhhdmUgc3RhcnRlZCBoaXMgc3Ryb2xsIGF0IGNvb3JkaW5hdGVzICg0LCA4KSwgbWV0IHRoZSBmaXJzdCBmcmllbmQsIHRha2VuIHR3byBzdGVwcyB0byB0aGUgcG9pbnQgKDYsIDYpLCBtZXQgdGhlIHNlY29uZCBmcmllbmQsIHRha2VuIHR3byBzdGVwcyB0byB0aGUgcG9pbnQgKDQsIDUpIGFuZCBtZXQgdGhlIHRoaXJkIGZyaWVuZCB0aGVyZS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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