시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 1 0 0 0.000%

문제

평면 위에 점이 여러 개 주어진다. 이 점을 모두 지나는 지그재그 선을 찾으려고 한다. 이때, 전환점(turning point)의 개수를 가장 적게 하려고 한다. 또, 전환점의 개수가 같은 경우에는 선의 길이가 가장 작은 것을 찾으려고 한다.

예를 들어, 아래와 같이 평면 위에 점이 9개가 있다고 하자.

지그재그 선은 여러 선분으로 이루어져 있고, 각 선분은 점을 두 개 이상 지나야 한다.

지그재그 선은 선이 꺽일 수 있는데, 이 꺽이는 지점을 전환점(turning point)라고 한다. 전환점은 주어진 점 위에 있을 수도 있고, 아닐 수도 있다.

왼쪽 지그재그 선의 길이: 8 + 3√2 ≃ 12.242641, 오른쪽 지그재그 선의 길이: 2√2 + (6 + 1/2) + 5√5/2 ≃ 14.918597

위의 그림은 주어진 점을 지나는 지그재그 선이고 두 선 모두 전환점의 개수는 3개이다. 왼쪽 지그재그 선의 길이는 오른쪽 지그재그 선의 길이보다 짧다. 또, 왼쪽 지그재그 선은 주어진 아홉 개의 점을 지나는 가장 짧은 지그재그 선이다.

전환점을 네 개 갖는 지그재그 선은 아래와 같다. 이 선의 길이는 위의 그림의 길이보다 짧지만, 전환점의 수가 더 많기 때문에 정답이 아니다.

아래와 같이 점이 7개 있고, 그 점을 잇는 두가지로 이었다고 하자. 이때, 왼쪽의 길이가 오른쪽보다 더 길지만, 정답은 왼쪽 그림이 된다. 그 이유는 지그재그 선의 모든 선분은 점을 두 개 이상 지나야 하기 때문이다.

점이 주어졌을 때, 지그재그 선을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 n이 주어진다. 다음 n개의 줄에는 점의 좌표가 주어진다.

모든 좌표는 음이 아닌 정수이고, 공백으로 구분되어 있다. n은 2이상 10이하의 자연수이고, x,y좌표는 0이상 10이하의 정수이다. 점의 순서는 별 의미가 없다.

출력

각 테스트 케이스에 대해서, 가장 적은 전환점을 갖는 지그재그 선 중 가장 짧은 것의 전환점의 개수와 길이를 출력한다. 선의 길이는 정답과의 오차가 0.0001까지 허용된다.

가장 적은 전환점의 개수는 최대 4개이며, 따라서 선분의 개수는 최대 5개가 된다.

예제 입력 1

2
0 0
10 9
4
0 0
3 1
0 3
3 3
10
2 2
4 2
6 2
2 4
4 4
6 4
2 6
4 6
6 6
3 3
10
0 0
2 0
4 0
0 2
2 2
4 2
0 4
2 4
4 4
6 8
9
0 0
1 0
3 0
0 1
1 1
3 1
0 2
1 2
2 2
10
0 0
1 0
0 1
1 1
9 9
9 10
10 9
10 10
0 2
10 8
10
0 0
0 10
2 0
2 1
2 7
2 10
5 1
6 7
9 2
10 9
0

예제 출력 1

0 13.45362405
1 18.48683298
3 24.14213562
4 24.94813673
3 12.24264069
3 60.78289622
3 502.7804353

힌트

첫 번째 데이터: 

두 번째 데이터: 

세 번째 데이터: 

네 번째 데이터: 

W3sicHJvYmxlbV9pZCI6IjM4OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgXHVjODEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjODEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM5YzBcdWIwOThcdWIyOTQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzgwNFx1ZDY1OFx1YzgxMCh0dXJuaW5nIHBvaW50KVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWM4MTBcdWM3NzQgOVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3oxLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE2MXB4OyBoZWlnaHQ6IDE0M3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzQwIFx1YzVlY1x1YjdlYyBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWM4MTBcdWM3NDQgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc0MCBcdWMxMjBcdWM3NzQgXHVhZWJkXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWFlYmRcdWM3NzRcdWIyOTQgXHVjOWMwXHVjODEwXHVjNzQ0IFx1YzgwNFx1ZDY1OFx1YzgxMCh0dXJuaW5nIHBvaW50KVx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODEwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjNTQ0XHViMmQwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvejIucG5nXCIgc3R5bGU9XCJ3aWR0aDogNDg2cHg7IGhlaWdodDogMTM3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NDogOCArIDMmcmFkaWM7MiBcdTIyNDMgMTIuMjQyNjQxLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzQ6IDImcmFkaWM7MiArICg2ICsgMVwvMikgKyA1JnJhZGljOzVcLzIgXHUyMjQzIDE0LjkxODU5NzxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4MTBcdWM3NDQgXHVjOWMwXHViMDk4XHViMjk0IFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NzRcdWFjZTAgXHViNDUwIFx1YzEyMCBcdWJhYThcdWI0NTAgXHVjODA0XHVkNjU4XHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAzXHVhYzFjXHVjNzc0XHViMmU0LiBcdWM2N2NcdWNhYmQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViY2Y0XHViMmU0IFx1YzllN1x1YjJlNC4gXHViNjEwLCBcdWM2N2NcdWNhYmQgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNTQ0XHVkNjQ5IFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVjOWMwXHViMDk4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjOWMwXHVhZGY4XHVjN2FjXHVhZGY4IFx1YzEyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODA0XHVkNjU4XHVjODEwXHVjNzQ0IFx1YjEyNCBcdWFjMWMgXHVhYzE2XHViMjk0IFx1YzljMFx1YWRmOFx1YzdhY1x1YWRmOCBcdWMxMjBcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVjNzc0IFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWJjZjRcdWIyZTQgXHVjOWU3XHVjOWMwXHViOWNjLCBcdWM4MDRcdWQ2NThcdWM4MTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YjM1NCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvejMucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTQ4cHg7IGhlaWdodDogOThweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4MTBcdWM3NzQgN1x1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YWRmOCBcdWM4MTBcdWM3NDQgXHVjNzg3XHViMjk0IFx1YjQ1MFx1YWMwMFx1YzljMFx1Yjg1YyBcdWM3NzRcdWM1YzhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMsIFx1YzY3Y1x1Y2FiZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjNjI0XHViOTc4XHVjYWJkXHViY2Y0XHViMmU0IFx1YjM1NCBcdWFlMzhcdWM5YzBcdWI5Y2MsIFx1YzgxNVx1YjJmNVx1Yzc0MCBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWMxMjBcdWJkODRcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3o0LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDQyN3B4OyBoZWlnaHQ6IDc0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YWNlMCwgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIG5cdWM3NDAgMlx1Yzc3NFx1YzBjMSAxMFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIHgseVx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAwXHVjNzc0XHVjMGMxIDEwXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjODEwXHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWJjYzQgXHVjNzU4XHViYmY4XHVhYzAwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjODA0XHVkNjU4XHVjODEwXHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWM5YzBcdWFkZjhcdWM3YWNcdWFkZjggXHVjMTIwIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc1OCBcdWM4MDRcdWQ2NThcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YWMwMCAwLjAwMDFcdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YzgwNFx1ZDY1OFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIDRcdWFjMWNcdWM3NzRcdWJhNzAsIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMxMjBcdWJkODRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1XHVhYzFjXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWIzNzBcdWM3NzRcdWQxMzA6Jm5ic3A7PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96aDEucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTYzcHg7IGhlaWdodDogMTY2cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHViMzcwXHVjNzc0XHVkMTMwOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvemgyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE1OHB4OyBoZWlnaHQ6IDE2NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YjM3MFx1Yzc3NFx1ZDEzMDombmJzcDs8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3poMy5wbmdcIiBzdHlsZT1cIndpZHRoOiAxNjJweDsgaGVpZ2h0OiAxNjJweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMTI0IFx1YmM4OFx1YzlmOCBcdWIzNzBcdWM3NzRcdWQxMzA6Jm5ic3A7PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96aDQucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTU4cHg7IGhlaWdodDogMTYxcHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWmlnemFnIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBzZXZlcmFsIHBvaW50cyBvbiBhIHBsYW5lLCBsZXQmcnNxdW87cyB0cnkgdG8gc29sdmUgYSBwdXp6bGUgY29ubmVjdGluZyB0aGVtIHdpdGggYSB6aWd6YWcgbGluZS4gVGhlIHB1enpsZSBpcyB0byBmaW5kIHRoZSB6aWd6YWcgbGluZSB0aGF0IHBhc3NlcyB0aHJvdWdoIGFsbCB0aGUgZ2l2ZW4gcG9pbnRzIHdpdGggdGhlIG1pbmltdW0gbnVtYmVyIG9mIHR1cm5zLiBNb3Jlb3Zlciwgd2hlbiB0aGVyZSBhcmUgc2V2ZXJhbCB6aWd6YWcgbGluZXMgd2l0aCB0aGUgbWluaW11bSBudW1iZXIgb2YgdHVybnMsIHRoZSBzaG9ydGVzdCBvbmUgYW1vbmcgdGhlbSBzaG91bGQgYmUgZm91bmQuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciBuaW5lIHBvaW50cyBnaXZlbiBpbiBGaWd1cmUgMTAuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvejEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQzcHg7IG9wYWNpdHk6MC45OyB3aWR0aDoxNjFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTA6IEdpdmVuIG5pbmUgcG9pbnRzPFwvcD5cclxuXHJcbjxwPkEgemlnemFnIGxpbmUgaXMgY29tcG9zZWQgb2Ygc2V2ZXJhbCBzdHJhaWdodCBsaW5lIHNlZ21lbnRzLiBIZXJlLCB0aGUgcnVsZSByZXF1ZXN0cyB0aGF0IGVhY2ggbGluZSBzZWdtZW50IHNob3VsZCBwYXNzIHRocm91Z2ggdHdvIG9yIG1vcmUgZ2l2ZW4gcG9pbnRzLjxcL3A+XHJcblxyXG48cD5BIHppZ3phZyBsaW5lIG1heSB0dXJuIGF0IHNvbWUgb2YgdGhlIGdpdmVuIHBvaW50cyBvciBhbnl3aGVyZSBlbHNlLiBUaGVyZSBtYXkgYmUgc29tZSBnaXZlbiBwb2ludHMgcGFzc2VkIG1vcmUgdGhhbiBvbmNlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3ppemEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTkwcHg7IHdpZHRoOjU0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxMTogWmlnemFnIGxpbmVzIHdpdGggdGhyZWUgdHVybmluZyBwb2ludHMuPFwvcD5cclxuXHJcbjxwPlR3byB6aWd6YWcgbGluZXMgd2l0aCB0aHJlZSB0dXJuaW5nIHBvaW50cyBhcmUgZGVwaWN0ZWQgaW4gRmlndXJlIDExIChhKSBhbmQgKGIpIGZvciB0aGUgc2FtZSBzZXQgb2YgZ2l2ZW4gcG9pbnRzIHNob3duIGluIEZpZ3VyZSAxMC4gVGhlIGxlbmd0aCBvZiB0aGUgemlnemFnIGxpbmUgaW4gRmlndXJlIDExIChhKSBpcyBzaG9ydGVyIHRoYW4gdGhhdCBpbiBGaWd1cmUgMTEgKGIpLiBJbiBmYWN0LCB0aGUgbGVuZ3RoIG9mIHRoZSB6aWd6YWcgbGluZSBpbiBGaWd1cmUgMTEgKGEpIGlzIHRoZSBzaG9ydGVzdCBzbyB0aGF0IGl0IGlzIHRoZSBzb2x1dGlvbiBmb3IgdGhlIG5pbmUgcG9pbnRzIGdpdmVuIGluIEZpZ3VyZSAxMC48XC9wPlxyXG5cclxuPHA+QW5vdGhlciB6aWd6YWcgbGluZSB3aXRoIGZvdXIgdHVybmluZyBwb2ludHMgaXMgZGVwaWN0ZWQgaW4gRmlndXJlIDEyLiBJdHMgbGVuZ3RoIGlzIHNob3J0ZXIgdGhhbiB0aG9zZSBpbiBGaWd1cmUgMTEsIGhvd2V2ZXIsIHRoZSBudW1iZXIgb2YgdHVybmluZyBwb2ludHMgaXMgZ3JlYXRlciB0aGFuIHRob3NlIGluIEZpZ3VyZSAxMSwgYW5kIHRodXMsIGl0IGlzIG5vdCB0aGUgc29sdXRpb24uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wveml6YTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIycHg7IHdpZHRoOjE2NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxMjogWmlnemFnIGxpbmUgd2l0aCBmb3VyIHR1cm5pbmcgcG9pbnRzLjxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgdHdvIHppZ3phZyBsaW5lcyB0aGF0IHBhc3NlcyBhbm90aGVyIHNldCBvZiBnaXZlbiBwb2ludHMgZGVwaWN0ZWQgaW4gRmlndXJlIDEzIChhKSBhbmQgKGIpLjxcL3A+XHJcblxyXG48cD5Cb3RoIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIHR1cm5pbmcgcG9pbnRzLCBhbmQgdGhlIGxpbmUgaW4gKGEpIGlzIGxvbmdlciB0aGFuIHRoYXQgaW4gKGIpLiBIb3dldmVyLCB0aGUgc29sdXRpb24gaXMgKGEpLCBiZWNhdXNlIG9uZSBvZiB0aGUgc2VnbWVudHMgb2YgdGhlIHppZ3phZyBsaW5lIGluIChiKSBwYXNzZXMgb25seSBvbmUgZ2l2ZW4gcG9pbnQsIHZpb2xhdGluZyB0aGUgcnVsZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC96aXphMy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDdweDsgd2lkdGg6NDQ0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEzOiBaaWd6YWcgbGluZSB3aXRoIHR3byB0dXJuaW5nIHBvaW50cyAoYSksIGFuZCBub3QgYSB6aWd6YWcgbGluZSBjb25jZXJuZWQgKGIpLjxcL3A+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBzb2x2ZXMgdGhpcyBwdXp6bGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIG9uZSB6ZXJvLiBFYWNoIGRhdGFzZXQgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5uXHJcbng8c3ViPjE8XC9zdWI+IHk8c3ViPjE8XC9zdWI+XHJcbi4uLlxyXG54PHN1Yj5uPFwvc3ViPiB5PHN1Yj5uPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPkV2ZXJ5IGlucHV0IGl0ZW0gaW4gYSBkYXRhc2V0IGlzIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIuIEl0ZW1zIGluIGEgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcblxyXG48cD5uIGlzIHRoZSBudW1iZXIgb2YgdGhlIGdpdmVuIHBvaW50cy4geDxzdWI+azxcL3N1Yj4gYW5kIHk8c3ViPms8XC9zdWI+IChrID0gMSwgLi4uLCBuKSBpbmRpY2F0ZSB0aGUgcG9zaXRpb24gb2YgdGhlIGstdGggcG9pbnQuIFRoZSBvcmRlciBvZiB0aGUgcG9pbnRzIGlzIG1lYW5pbmdsZXNzLiBZb3UgY2FuIGFzc3VtZSB0aGF0IDIgJmxlOyBuICZsZTsgMTAsIDAgJmxlOyB4PHN1Yj5rPFwvc3ViPiAmbGU7IDEwLCBhbmQgMCAmbGU7IHk8c3ViPms8XC9zdWI+ICZsZTsgMTAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHR1cm5pbmcgcG9pbnRzIGFuZCB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCB6aWd6YWcgbGluZSB3aXRoIHRoYXQgbnVtYmVyIG9mIHR1cm5pbmcgcG9pbnRzIHNob3VsZCBiZSBwcmludGVkLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZSBpbiBhIGxpbmUuIFRoZSBsZW5ndGggc2hvdWxkIGJlIGluIGEgZGVjaW1hbCBmcmFjdGlvbiB3aXRoIGFuIGVycm9yIGxlc3MgdGhhbiAwLjAwMDEgKD0gMS4wICZ0aW1lczsgMTA8c3VwPiZtaW51czs0PFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHR1cm5pbmcgcG9pbnRzIGlzIGF0IG1vc3QgZm91ciwgdGhhdCBpcywgdGhlIG51bWJlciBvZiBsaW5lIHNlZ21lbnRzIGlzIGF0IG1vc3QgZml2ZS48XC9wPlxyXG5cclxuPHA+VGhlIGV4YW1wbGUgc29sdXRpb25zIGZvciB0aGUgZmlyc3QgZm91ciBkYXRhc2V0cyBpbiB0aGUgc2FtcGxlIGlucHV0IGFyZSBkZXBpY3RlZCBpbiBGaWd1cmUgMTQgYW5kIDE1LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3ppemE0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjY5MHB4OyB3aWR0aDo2MTNweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2008 in Aizu J번