시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 67 32 29 54.717%

문제

상근이는 네비게이션을 하나 만들었다. 이 네비게이션은 다른 기계와 다르게 최단 경로만 구하지 않는다. 상근이는 매일 아침마다 근처 공원을 산책하면서 네비게이션의 성능을 테스트해 보려고 한다.

매일 아침 네비게이션은 산책 경로를 하나 제안한다. 경로는 여러 개의 선분으로 이루어져 있고, 각 선분은 두 정수 (X, Y)로 나타낼 수 있으며, 이동하는 방향과 거리를 나타낸다.

예를 들어, 왼쪽 그림은 4개의 선분으로 이루어진 경로이다. 첫 번째 선분은 (-1, 1), 두 번째 선분은 (1, 1), 세 번째는 (1, 0) 마지막 네번째는 (0, -2)로 나타낼 수 있다.

경로가 끝나는 최종 위치는 시작한 위치에서 동쪽으로 1미터 떨어져 있다.

상근이는 산책을 마치는 위치가 시작한 위치와 많이 떨어져 있는 것을 싫어하기 때문에, 선분 하나를 제거하려고 한다. 즉, 산책 경로에 있는 선분 중 하나를 제거해 시작 위치와 마지막 위치 사이의 거리를 최소로 만드려고 한다.

예를 들어, 상근이가 그림에서 세 번째 선분을 없애면 오른쪽 그림과 같이 되고, 산책을 마치는 위치가 시작한 위치와 정확하게 일치하게 된다. 

네비게이션이 제안한 산책 경로를 그대로 사용할 때, 산책을 마치는 위치가 시작한 위치와 얼마나 떨어져있는 지를 구하고, 그 경로에서 선분 하나를 제거했을 때, 시작 위치와 마지막 위치 사이 거리의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선분의 개수 N (1 < N ≤ 30)이 주어진다. 다음 N개 줄에는 각 선분을 나타내는 두 정수 X와 Y가 주어진다. (-1000 ≤ X, Y ≤ 1000)

출력

첫째 줄에 입력으로 주어진 산책 경로를 그대로 사용했을 때, 산책을 마치는 위치를 출력한다. (시작한 위치의 좌표를 (0,0)이라고 한다)

둘째 줄에는 선분을 하나 제거했을 때, 산책을 마치는 위치와 시작한 위치 사이 거리의 최소값을 반올림해 소수점 둘째 자리까지 출력한다.

예제 입력 1

4
-1 1
1 1
1 0
0 -2

예제 출력 1

1 0
0.00
W3sicHJvYmxlbV9pZCI6IjMwOTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYjBcdWNjNDUgXHVhY2JkXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMTI0XHViZTQ0XHVhYzhjXHVjNzc0XHVjMTU4XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWIxMjRcdWJlNDRcdWFjOGNcdWM3NzRcdWMxNThcdWM3NDAgXHViMmU0XHViOTc4IFx1YWUzMFx1YWNjNFx1YzY0MCBcdWIyZTRcdWI5NzRcdWFjOGMgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1YjljYyBcdWFkNmNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OFx1YjljOFx1YjJlNCBcdWFkZmNcdWNjOTggXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzBiMFx1Y2M0NVx1ZDU1OFx1YmE3NFx1YzExYyBcdWIxMjRcdWJlNDRcdWFjOGNcdWM3NzRcdWMxNThcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQ0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1ZDU3NCBcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTRcdWM3N2MgXHVjNTQ0XHVjZTY4IFx1YjEyNFx1YmU0NFx1YWM4Y1x1Yzc3NFx1YzE1OFx1Yzc0MCBcdWMwYjBcdWNjNDUgXHVhY2JkXHViODVjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWM1NDhcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjMTIwXHViZDg0XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggKFgsIFkpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVhY2ZjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgNFx1YWMxY1x1Yzc1OCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMxMjBcdWJkODRcdWM3NDAgKC0xLCAxKSwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMxMjBcdWJkODRcdWM3NDAgKDEsIDEpLCBcdWMxMzggXHViYzg4XHVjOWY4XHViMjk0ICgxLCAwKSBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMTI0XHViYzg4XHVjOWY4XHViMjk0ICgwLCAtMilcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjZDVjXHVjODg1IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjNkOVx1Y2FiZFx1YzczY1x1Yjg1YyAxXHViYmY4XHVkMTMwIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcm91dGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTY2cHg7IHdpZHRoOjQ3MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYjBcdWNjNDVcdWM3NDQgXHViOWM4XHVjZTU4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjljZVx1Yzc3NCBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWMyZWJcdWM1YjRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMxMjBcdWJkODQgXHVkNTU4XHViMDk4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVjMGIwXHVjYzQ1IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViZDg0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWM2NDAgXHViOWM4XHVjOWMwXHViOWM5IFx1YzcwNFx1Y2U1OCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMTIwXHViZDg0XHVjNzQ0IFx1YzVjNlx1YzU2MFx1YmE3NCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNThcdWM2NDAgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjEyNFx1YmU0NFx1YWM4Y1x1Yzc3NFx1YzE1OFx1Yzc3NCBcdWM4MWNcdWM1NDhcdWQ1NWMgXHVjMGIwXHVjYzQ1IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YjU0YywgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM1YmNcdWI5YzhcdWIwOTggXHViNWE4XHVjNWI0XHVjODM4XHVjNzg4XHViMjk0IFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHVjMTIwXHViZDg0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWM3MDRcdWNlNTggXHVjMGFjXHVjNzc0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSAmbHQ7IE4gJmxlOyAzMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBYXHVjNjQwIFlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwMDAgJmxlOyBYLCBZICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGIwXHVjYzQ1IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgKDAsMClcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjODFjXHVhYzcwXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWM2NDAgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzcwNFx1Y2U1OCBcdWMwYWNcdWM3NzQgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NzQgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwOTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTRVROSkEiLCJkZXNjcmlwdGlvbiI6IjxwPk1hcmlvIGdvdCBhIG5ldyBwb3J0YWJsZSBuYXZpZ2F0aW9uYWwgZGV2aWNlLiBUaGlzIG9uZSBzcGVjaWFsIGJlY2F1c2UgaXQgbm90IG1lYW50IHRvIGJlIHVzZWQgZm9yIGZpbmQgdGhlIHNob3J0ZXN0IHJvdXRlLiBJdCBpcyB1c2VkIGZvciBhIFN1bmRheSB3YWxrIHRocm91Z2ggdGhlIG5lYXJieSBiZWF1dGlmdWwgcGFyay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgZGF5IHRoZSBkZXZpY2UgcHJvcG9zZXMgYSByb3V0ZSBmb3IgYSB3YWxrLiBBIHJvdXRlIGlzIGNvbXBvc2VkIG9mIHNldmVyYWwgc2VnbWVudHMuIEVhY2ggc2VnbWVudCBpcyBkZXNjcmliZWQgd2l0aCB0d28gaW50ZWdlcnMgKFgsIFkpLCB0aGUgcmVsYXRpdmUgbW92ZW1lbnQgcG9zaXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgcHJvcG9zZWQgcm91dGUgaW4gdGhlIGxlZnQgaWxsdXN0cmF0aW9uIHRoYXQgaXMgY29tcG9zZWQgb2YgZm91ciBzZWdtZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rmlyc3Qgc2VnbWVudCBpcyBkZXNjcmliZWQgYXMgKC0xLCAxKSwgc2Vjb25kIHNlZ21lbnQgYXMgKDEsIDEpLCB0aGlyZCBhcyAoMSwgMCkgYW5kIGZpbmFsbHkgZm91cnRoIHNlZ21lbnQgYXMgKDAsIC0yKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpbmFsIHBvc2l0aW9uIG9mIHRoZSBwcm9wb3NlZCByb3V0ZSBmaW5pc2hlcyB0aGUgd2FsayAxIG1ldGVyIGVhc3Qgb2YgdGhlIHN0YXJ0aW5nIHBvc2l0aW9uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcm91dGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTY2cHg7IHdpZHRoOjQ3MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1hcmlvIGRvZXNuJiMzOTt0IHdhbnQgdG8gZmluaXNoIHRoZSB3YWxrIHRvbyBmYXIgZnJvbSB0aGUgc3RhcnRpbmcgcG9zaXRpb24sIHNvIGhlIGRlY2lkZWQgdG8gcmVtb3ZlIGV4YWN0bHkgb25lIHNlZ21lbnQuIEhlIHdpbGwgcGljayBhIHNlZ21lbnQgc28gdGhhdCB0aGUgbmV3IHJvdXRlIGZpbmlzaGVzIGFzIGNsb3NlIGFzIHBvc3NpYmxlIHRvIHRoZSBzdGFydGluZyBwb3NpdGlvbi4gRm9yIGV4YW1wbGUsIGlmIE1hcmlvIHJlbW92ZXMgdGhpcmQgc2VnbWVudCBvZiB0aGUgcHJvcG9zZWQgcm91dGUgKGFzIGluIHRoZSByaWdodCBpbGx1c3RyYXRpb24pIGhlIHdpbGwgZmluaXNoIGV4YWN0bHkgb24gdGhlIHN0YXJ0aW5nIHBvc2l0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSB0aGUgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBmaW5hbCBwb3NpdGlvbiBvZiB0aGUgcHJvcG9zZWQgcm91dGUsIGFuZCB3aWxsIGRldGVybWluZSB0aGUgc2hvcnRlc3QgcG9zc2libGUgZGlzdGFuY2UgZnJvbSBzdGFydCB0byBmaW5pc2ggaWYgaGUgcmVtb3ZlcyBvbmUgc2VnbWVudCBvZiB0aGUgcm91dGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBOICgxICZsdDsgTiAmbGU7IDMwKSwgdGhlIG51bWJlciBvZiBzZWdtZW50cyBvbiB0aGUgcHJvcG9zZWQgcm91dGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgZWFjaCBYIGFuZCBZICgtMTAwMCAmbGU7IFgsWSAmbGU7IDEwMDApIGRlc2NyaWJpbmcgYSByb3V0ZSBzZWdtZW50LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG91dHB1dCB0d28gaW50ZWdlcnMgWCBhbmQgWSB0aGF0IGRlc2NyaWJlIHRoZSBmaW5hbCBwb3NpdGlvbiBvZiB0aGUgcHJvcG9zZWQgcm91dGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgbGluZSBvdXRwdXQgb25lIHJlYWwgbnVtYmVyIChyb3VuZGVkIHRvIHR3byBkZWNpbWFsIHBsYWNlcyksIHRoZSBzaG9ydGVzdCBwb3NzaWJsZSBkaXN0YW5jZSBmcm9tIHN0YXJ0IHRvIGZpbmlzaCBpZiBNYXJpbyByZW1vdmVzIG9uZSBzZWdtZW50IG9mIHRoZSByb3V0ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > School Competition - Juniors 1번

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