시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 34 31 56.364%

문제

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

매일 아침 네비게이션은 산책 경로를 하나 제안한다. 경로는 여러 개의 선분으로 이루어져 있고, 각 선분은 두 정수 (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+XHJcblxyXG48cD5cdWI5ZTRcdWM3N2MgXHVjNTQ0XHVjZTY4IFx1YjEyNFx1YmU0NFx1YWM4Y1x1Yzc3NFx1YzE1OFx1Yzc0MCBcdWMwYjBcdWNjNDUgXHVhY2JkXHViODVjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWM1NDhcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVjMTIwXHViZDg0XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggKFgsIFkpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVhY2ZjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgNFx1YWMxY1x1Yzc1OCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMxMjBcdWJkODRcdWM3NDAgKC0xLCAxKSwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMxMjBcdWJkODRcdWM3NDAgKDEsIDEpLCBcdWMxMzggXHViYzg4XHVjOWY4XHViMjk0ICgxLCAwKSBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMTI0IFx1YmM4OFx1YzlmOFx1YjI5NCAoMCwgLTIpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWI4NWNcdWFjMDAgXHViMDVkXHViMDk4XHViMjk0IFx1Y2Q1Y1x1Yzg4NSBcdWM3MDRcdWNlNThcdWIyOTQgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWIzZDlcdWNhYmRcdWM3M2NcdWI4NWMgMVx1YmJmOFx1ZDEzMCBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3JvdXRlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NnB4OyB3aWR0aDo0NzFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWI5Y2VcdWM3NzQgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjMmViXHVjNWI0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMTIwXHViZDg0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzBiMFx1Y2M0NSBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzEyMFx1YmQ4NCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU3NCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWM3MDRcdWNlNTggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWM1YzZcdWM1NjBcdWJhNzQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWMwYjBcdWNjNDVcdWM3NDQgXHViOWM4XHVjZTU4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM3N2NcdWNlNThcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIxMjRcdWJlNDRcdWFjOGNcdWM3NzRcdWMxNThcdWM3NzQgXHVjODFjXHVjNTQ4XHVkNTVjIFx1YzBiMFx1Y2M0NSBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZGY4XHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWI1NGMsIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTQgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNThcdWM2NDAgXHVjNWJjXHViOWM4XHViMDk4IFx1YjVhOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1YzEyMFx1YmQ4NCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzA0XHVjZTU4IFx1YzBhY1x1Yzc3NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMjBcdWJkODRcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmx0OyBOICZsZTsgMzApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMxMjBcdWJkODRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMTggWFx1YzY0MCBZXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xMDAwICZsZTsgWCwgWSAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzBiMFx1Y2M0NSBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZGY4XHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTQgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNThcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjICgwLDApXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NDQgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWI5YzhcdWNlNThcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNTggXHVjMGFjXHVjNzc0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHViYzE4XHVjNjJjXHViOWJjXHVkNTc0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0VUTkpBIiwiZGVzY3JpcHRpb24iOiI8cD5NYXJpbyBnb3QgYSBuZXcgcG9ydGFibGUgbmF2aWdhdGlvbmFsIGRldmljZS4gVGhpcyBvbmUgc3BlY2lhbCBiZWNhdXNlIGl0IG5vdCBtZWFudCB0byBiZSB1c2VkIGZvciBmaW5kIHRoZSBzaG9ydGVzdCByb3V0ZS4gSXQgaXMgdXNlZCBmb3IgYSBTdW5kYXkgd2FsayB0aHJvdWdoIHRoZSBuZWFyYnkgYmVhdXRpZnVsIHBhcmsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IGRheSB0aGUgZGV2aWNlIHByb3Bvc2VzIGEgcm91dGUgZm9yIGEgd2Fsay4gQSByb3V0ZSBpcyBjb21wb3NlZCBvZiBzZXZlcmFsIHNlZ21lbnRzLiBFYWNoIHNlZ21lbnQgaXMgZGVzY3JpYmVkIHdpdGggdHdvIGludGVnZXJzIChYLCBZKSwgdGhlIHJlbGF0aXZlIG1vdmVtZW50IHBvc2l0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIHByb3Bvc2VkIHJvdXRlIGluIHRoZSBsZWZ0IGlsbHVzdHJhdGlvbiB0aGF0IGlzIGNvbXBvc2VkIG9mIGZvdXIgc2VnbWVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZpcnN0IHNlZ21lbnQgaXMgZGVzY3JpYmVkIGFzICgtMSwgMSksIHNlY29uZCBzZWdtZW50IGFzICgxLCAxKSwgdGhpcmQgYXMgKDEsIDApIGFuZCBmaW5hbGx5IGZvdXJ0aCBzZWdtZW50IGFzICgwLCAtMikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaW5hbCBwb3NpdGlvbiBvZiB0aGUgcHJvcG9zZWQgcm91dGUgZmluaXNoZXMgdGhlIHdhbGsgMSBtZXRlciBlYXN0IG9mIHRoZSBzdGFydGluZyBwb3NpdGlvbjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3JvdXRlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NnB4OyB3aWR0aDo0NzFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NYXJpbyBkb2VzbiYjMzk7dCB3YW50IHRvIGZpbmlzaCB0aGUgd2FsayB0b28gZmFyIGZyb20gdGhlIHN0YXJ0aW5nIHBvc2l0aW9uLCBzbyBoZSBkZWNpZGVkIHRvIHJlbW92ZSBleGFjdGx5IG9uZSBzZWdtZW50LiBIZSB3aWxsIHBpY2sgYSBzZWdtZW50IHNvIHRoYXQgdGhlIG5ldyByb3V0ZSBmaW5pc2hlcyBhcyBjbG9zZSBhcyBwb3NzaWJsZSB0byB0aGUgc3RhcnRpbmcgcG9zaXRpb24uIEZvciBleGFtcGxlLCBpZiBNYXJpbyByZW1vdmVzIHRoaXJkIHNlZ21lbnQgb2YgdGhlIHByb3Bvc2VkIHJvdXRlIChhcyBpbiB0aGUgcmlnaHQgaWxsdXN0cmF0aW9uKSBoZSB3aWxsIGZpbmlzaCBleGFjdGx5IG9uIHRoZSBzdGFydGluZyBwb3NpdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgdGhlIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSB0aGUgZmluYWwgcG9zaXRpb24gb2YgdGhlIHByb3Bvc2VkIHJvdXRlLCBhbmQgd2lsbCBkZXRlcm1pbmUgdGhlIHNob3J0ZXN0IHBvc3NpYmxlIGRpc3RhbmNlIGZyb20gc3RhcnQgdG8gZmluaXNoIGlmIGhlIHJlbW92ZXMgb25lIHNlZ21lbnQgb2YgdGhlIHJvdXRlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBjb250YWlucyBvbmUgTiAoMSAmbHQ7IE4gJmxlOyAzMCksIHRoZSBudW1iZXIgb2Ygc2VnbWVudHMgb24gdGhlIHByb3Bvc2VkIHJvdXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIGVhY2ggWCBhbmQgWSAoLTEwMDAgJmxlOyBYLFkgJmxlOyAxMDAwKSBkZXNjcmliaW5nIGEgcm91dGUgc2VnbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSBvdXRwdXQgdHdvIGludGVnZXJzIFggYW5kIFkgdGhhdCBkZXNjcmliZSB0aGUgZmluYWwgcG9zaXRpb24gb2YgdGhlIHByb3Bvc2VkIHJvdXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIGxpbmUgb3V0cHV0IG9uZSByZWFsIG51bWJlciAocm91bmRlZCB0byB0d28gZGVjaW1hbCBwbGFjZXMpLCB0aGUgc2hvcnRlc3QgcG9zc2libGUgZGlzdGFuY2UgZnJvbSBzdGFydCB0byBmaW5pc2ggaWYgTWFyaW8gcmVtb3ZlcyBvbmUgc2VnbWVudCBvZiB0aGUgcm91dGUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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