시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 15 13 37.143%

문제

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

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

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

출처

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

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