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

문제

Freddy Frog는 호수 한 가운데 돌에 앉아 있다. 그는 불현듯 또 다른 돌에 앉아 있는 Fiona Frog를 인식했다. 그는 그녀에게 갈 계획을 세웠지만, 물이 더럽고 관광객의 선크림으로 가득 차있었기 때문에, 그는 수영을 하지 않고 점프를 통해그녀에게 가고자 했다. 

불행히도 Fiona의 돌은 점프 범위를 벗어나 있다. 그러므로 Freddy는 다른 돌을 거쳐 여러 번의 점프로 그녀에게 가기로 마음 먹었다.

주어진 순서로 점프하기 위해, frog의 점프 범위는 적어도 순서의 가장 멀리 먼 거리의 점프만큼은 되어야 한다.

두 돌 사이의 the frog distance (사람들이 최소 거리라 부르는) 는 모든 가능한 두 돌 사이의 경로의 필요한 최소한의 점프 범위로 정의할 수 있다.

당신은 주어진 Freddy의 돌, Fiona의 돌 그리고 호수의 모든 다른 돌을 좌표로 받게 된다. 당신의 일은 Freddy 돌과 Fiona 돌의 the frog distance를 계산하는 것이다. 

입력

입력 파일은 하나 혹은 그 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 번째 줄은 n개의 돌을 포함한다. (각각의 2nn lines은 두 개의 정수 xi,yi 를 포함한다.) 돌 #1은 Freddy의 돌이고, 돌 #2는 Fiona의 돌 그리고 다른 n-2 돌은 비어 있는 돌이다. 각 테스트 케이스 사이에는 공백 행이 있다. n을 위한 값이 zero (0)가 될 경우 입력은 종료된다. 

출력

각각의 테스트 케이스에서 "Scenario #x" 문장과 "Frog Distance = y" 문장을 출력한다. 여기서 x는 테스트 케이스의 수로 대체된다 (1부터 번호가 매겨진다). y는 적절한 소수점 셋째 자리의 실수로 대체될 수 있다. 마지막 케이스까지 각 테스트 케이스 뒤에는 공백 행을 출력해라.

예제 입력 1

2
0 0
3 4

3
17 4
19 4
18 5

0

예제 출력 1

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414
W3sicHJvYmxlbV9pZCI6IjY1OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI4NWNcdWFjNzAiLCJkZXNjcmlwdGlvbiI6IjxwPkZyZWRkeSBGcm9nXHViMjk0IFx1ZDYzOFx1YzIxOCBcdWQ1NWMgXHVhYzAwXHVjNmI0XHViMzcwIFx1YjNjY1x1YzVkMCBcdWM1NDlcdWM1NDQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWIyOTQgXHViZDg4XHVkNjA0XHViNGVmJm5ic3A7XHViNjEwIFx1YjJlNFx1Yjk3OCBcdWIzY2NcdWM1ZDAgXHVjNTQ5XHVjNTQ0IFx1Yzc4OFx1YjI5NCZuYnNwO0Zpb25hIEZyb2dcdWI5N2MgXHVjNzc4XHVjMmRkXHVkNTg4XHViMmU0LiBcdWFkZjhcdWIyOTQgXHVhZGY4XHViMTQwXHVjNWQwXHVhYzhjIFx1YWMwOCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmUwXHVjOWMwXHViOWNjLCBcdWJiM2NcdWM3NzQgXHViMzU0XHViN2ZkXHVhY2UwIFx1YWQwMFx1YWQxMVx1YWMxZFx1Yzc1OCBcdWMxMjBcdWQwNmNcdWI5YmNcdWM3M2NcdWI4NWMgXHVhYzAwXHViNGRkIFx1Y2MyOFx1Yzc4OFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWRmOFx1YjI5NCBcdWMyMThcdWM2MDFcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM4MTBcdWQ1MDRcdWI5N2MgXHVkMWI1XHVkNTc0XHVhZGY4XHViMTQwXHVjNWQwXHVhYzhjIFx1YWMwMFx1YWNlMFx1Yzc5MCBcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmQ4OFx1ZDU4OVx1ZDc4OFx1YjNjNCBGaW9uYVx1Yzc1OCZuYnNwO1x1YjNjY1x1Yzc0MCBcdWM4MTBcdWQ1MDQgXHViYzk0XHVjNzA0XHViOTdjIFx1YmM5N1x1YzViNFx1YjA5OCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmJjMFx1Yjg1YyZuYnNwO0ZyZWRkeVx1YjI5NCBcdWIyZTRcdWI5NzggXHViM2NjXHVjNzQ0IFx1YWM3MFx1Y2NkMCBcdWM1ZWNcdWI3ZWMgXHViYzg4XHVjNzU4Jm5ic3A7XHVjODEwXHVkNTA0XHViODVjIFx1YWRmOFx1YjE0MFx1YzVkMFx1YWM4YyBcdWFjMDBcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjIFx1YmEzOVx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NThcdWFlMzAmbmJzcDtcdWM3MDRcdWQ1NzQsIGZyb2dcdWM3NTgmbmJzcDtcdWM4MTBcdWQ1MDQgXHViYzk0XHVjNzA0XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWMyMWNcdWMxMWNcdWM3NTgmbmJzcDtcdWFjMDBcdWM3YTUgXHViYTQwXHViOWFjIFx1YmEzYyBcdWFjNzBcdWI5YWNcdWM3NTggXHVjODEwXHVkNTA0XHViOWNjXHVkMDdjXHVjNzQwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWIzY2MgXHVjMGFjXHVjNzc0XHVjNzU4Jm5ic3A7dGhlJm5ic3A7ZnJvZyBkaXN0YW5jZSAoXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0Jm5ic3A7XHVjZDVjXHVjMThjIFx1YWM3MFx1YjlhY1x1Yjc3YyBcdWJkODBcdWI5NzRcdWIyOTQpIFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjQ1MCBcdWIzY2MgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCZuYnNwO1x1ZDU0NFx1YzY5NFx1ZDU1YyZuYnNwO1x1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWM4MTBcdWQ1MDQgXHViYzk0XHVjNzA0XHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWM0Jm5ic3A7RnJlZGR5XHVjNzU4Jm5ic3A7XHViM2NjLCBGaW9uYVx1Yzc1OCBcdWIzY2MgXHVhZGY4XHViOWFjXHVhY2UwIFx1ZDYzOFx1YzIxOFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMmU0XHViOTc4IFx1YjNjY1x1Yzc0NCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzU4IFx1Yzc3Y1x1Yzc0MCBGcmVkZHkgXHViM2NjXHVhY2ZjIEZpb25hJm5ic3A7XHViM2NjXHVjNzU4Jm5ic3A7dGhlIGZyb2cgZGlzdGFuY2VcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM3NDAgXHVkNTU4XHViMDk4IFx1ZDYzOVx1Yzc0MCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBuXHVhYzFjXHVjNzU4IFx1YjNjY1x1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuIChcdWFjMDFcdWFjMDFcdWM3NTgmbmJzcDsybm4gbGluZXNcdWM3NDAgXHViNDUwJm5ic3A7XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCZuYnNwO3hpLHlpIFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuKSZuYnNwO1x1YjNjYyAjMVx1Yzc0MCZuYnNwO0ZyZWRkeVx1Yzc1OCBcdWIzY2NcdWM3NzRcdWFjZTAsIFx1YjNjYyAjMlx1YjI5NCZuYnNwO0Zpb25hXHVjNzU4IFx1YjNjYyZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWI5Nzggbi0yIFx1YjNjY1x1Yzc0MCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjNjY1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCZuYnNwO1x1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCZuYnNwO1x1YWNmNVx1YmMzMSBcdWQ1ODlcdWM3NzQgXHVjNzg4XHViMmU0LiBuXHVjNzQ0IFx1YzcwNFx1ZDU1YyBcdWFjMTJcdWM3NzQmbmJzcDt6ZXJvICgwKVx1YWMwMCBcdWI0MjAgXHVhY2JkXHVjNmIwIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMmbmJzcDsmcXVvdDtTY2VuYXJpbyAjeCZxdW90OyBcdWJiMzhcdWM3YTVcdWFjZmMmbmJzcDsmcXVvdDtGcm9nIERpc3RhbmNlID0mbmJzcDt5JnF1b3Q7IFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyB4XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViODVjIFx1YjMwMFx1Y2NiNFx1YjQxY1x1YjJlNCAoMVx1YmQ4MFx1ZDEzMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjOWM0XHViMmU0KS4geVx1YjI5NCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOCBcdWM3OTBcdWI5YWNcdWM3NTggXHVjMmU0XHVjMjE4XHViODVjIFx1YjMwMFx1Y2NiNFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjZjAwXHVjNzc0XHVjMmE0XHVhZTRjXHVjOWMwIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0Jm5ic3A7XHViNGE0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMSBcdWQ1ODlcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY1OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGcm9nZ2VyIiwiZGVzY3JpcHRpb24iOiJcblxuPHA+XG48XC9wPjxwPlxuXG5GcmVkZHkgRnJvZyBpcyBzaXR0aW5nIG9uIGEgc3RvbmUgaW4gdGhlIG1pZGRsZSBvZiBhIGxha2UuIFN1ZGRlbmx5IGhlXG5ub3RpY2VzIEZpb25hIEZyb2cgd2hvIGlzIHNpdHRpbmcgb24gYW5vdGhlciBzdG9uZS4gSGUgcGxhbnMgdG8gdmlzaXQgaGVyLFxuYnV0IHNpbmNlIHRoZSB3YXRlciBpcyBkaXJ0eSBhbmQgZnVsbCBvZiB0b3VyaXN0cycgc3Vuc2NyZWVuLCBoZSB3YW50cyB0b1xuYXZvaWQgc3dpbW1pbmcgYW5kIGluc3RlYWQgcmVhY2ggaGVyIGJ5IGp1bXBpbmcuXG48XC9wPjxwPlxuVW5mb3J0dW5hdGVseSBGaW9uYSdzIHN0b25lIGlzIG91dCBvZiBoaXMganVtcCByYW5nZS4gVGhlcmVmb3JlIEZyZWRkeVxuY29uc2lkZXJzIHRvIHVzZSBvdGhlciBzdG9uZXMgYXMgaW50ZXJtZWRpYXRlIHN0b3BzIGFuZCByZWFjaCBoZXIgYnlcbmEgc2VxdWVuY2Ugb2Ygc2V2ZXJhbCBzbWFsbCBqdW1wcy5cbjxcL3A+PHA+XG5UbyBleGVjdXRlIGEgZ2l2ZW4gc2VxdWVuY2Ugb2YganVtcHMsIGEgZnJvZydzIGp1bXAgcmFuZ2Ugb2J2aW91c2x5IG11c3QgYmUgYXRcbmxlYXN0IGFzIGxvbmcgYXMgdGhlIGxvbmdlc3QganVtcCBvY2N1cmluZyBpbiB0aGUgc2VxdWVuY2UuXG48XC9wPjxwPlxuVGhlIDxpPmZyb2cgZGlzdGFuY2U8XC9pPiAoaHVtYW5zIGFsc28gY2FsbCBpdCA8aT5taW5pbWF4IGRpc3RhbmNlPFwvaT4pXG5iZXR3ZWVuIHR3byBzdG9uZXMgdGhlcmVmb3JlIGlzIGRlZmluZWQgYXMgdGhlIG1pbmltdW0gbmVjZXNzYXJ5XG5qdW1wIHJhbmdlIG92ZXIgYWxsIHBvc3NpYmxlIHBhdGhzIGJldHdlZW4gdGhlIHR3byBzdG9uZXMuIFxuPFwvcD48cD5cbllvdSBhcmUgZ2l2ZW4gdGhlIGNvb3JkaW5hdGVzIG9mIEZyZWRkeSdzIHN0b25lLCBGaW9uYSdzIHN0b25lIGFuZCBhbGxcbm90aGVyIHN0b25lcyBpbiB0aGUgbGFrZS4gWW91ciBqb2IgaXMgdG8gY29tcHV0ZSB0aGUgPGk+ZnJvZyBkaXN0YW5jZTxcL2k+XG5iZXR3ZWVuIEZyZWRkeSdzIGFuZCBGaW9uYSdzIHN0b25lLlxuXG48XC9wPiIsImlucHV0IjoiXG5cblRoZSBpbnB1dCBmaWxlIHdpbGwgY29udGFpbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBcblRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIHdpbGwgY29udGFpbiB0aGUgbnVtYmVyIG9mIHN0b25lcyA8aT5uPFwvaT5cbigybm4gbGluZXMgZWFjaCBjb250YWluIHR3byBpbnRlZ2Vyc1xueDxzdWI+aTxcL3N1Yj4seTxzdWI+aTxcL3N1Yj5cbigwIGkseTxzdWI+aTxcL3N1Yj4gaS5cblN0b25lICMxIGlzIEZyZWRkeSdzIHN0b25lLCBzdG9uZSAjMiBpcyBGaW9uYSdzIHN0b25lLCB0aGUgb3RoZXIgPGk+bjxcL2k+LTJcbnN0b25lcyBhcmUgdW5vY2N1cGllZC5cblRoZXJlJ3MgYSBibGFuayBsaW5lIGZvbGxvd2luZyBlYWNoIHRlc3QgY2FzZS5cbklucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSB2YWx1ZSBvZiB6ZXJvICgwKSBmb3IgPGk+bjxcL2k+LlxuXG4iLCJvdXRwdXQiOiJcblxuRm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBhIGxpbmUgc2F5aW5nIFwiU2NlbmFyaW8gIzxpPng8XC9pPlwiIGFuZCBhIGxpbmVcbnNheWluZyBcIkZyb2cgRGlzdGFuY2UgPSA8aT55PFwvaT5cIiB3aGVyZSA8aT54PFwvaT4gaXMgcmVwbGFjZWQgYnkgdGhlIHRlc3RcbmNhc2UgbnVtYmVyICh0aGV5IGFyZSBudW1iZXJlZCBmcm9tIDEpIGFuZCA8aT55PFwvaT4gaXMgcmVwbGFjZWQgYnkgdGhlXG5hcHByb3ByaWF0ZSByZWFsIG51bWJlciwgcHJpbnRlZCB0byB0aHJlZSBkZWNpbWFscy5cblB1dCBhIGJsYW5rIGxpbmUgYWZ0ZXIgZWFjaCB0ZXN0IGNhc2UsIGV2ZW4gYWZ0ZXIgdGhlIGxhc3Qgb25lLlxuXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=