시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWM0Jm5ic3A7RnJlZGR5XHVjNzU4Jm5ic3A7XHViM2NjLCBGaW9uYVx1Yzc1OCBcdWIzY2MgXHVhZGY4XHViOWFjXHVhY2UwIFx1ZDYzOFx1YzIxOFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMmU0XHViOTc4IFx1YjNjY1x1Yzc0NCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzU4IFx1Yzc3Y1x1Yzc0MCBGcmVkZHkgXHViM2NjXHVhY2ZjIEZpb25hJm5ic3A7XHViM2NjXHVjNzU4Jm5ic3A7dGhlIGZyb2cgZGlzdGFuY2VcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM3NDAgXHVkNTU4XHViMDk4IFx1ZDYzOVx1Yzc0MCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIG5cdWFjMWNcdWM3NTggXHViM2NjXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4gKFx1YWMwMVx1YWMwMVx1Yzc1OCZuYnNwOzJubiBsaW5lc1x1Yzc0MCBcdWI0NTAmbmJzcDtcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4Jm5ic3A7eGkseWkgXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4pJm5ic3A7XHViM2NjICMxXHVjNzQwJm5ic3A7RnJlZGR5XHVjNzU4IFx1YjNjY1x1Yzc3NFx1YWNlMCwgXHViM2NjICMyXHViMjk0Jm5ic3A7RmlvbmFcdWM3NTggXHViM2NjJm5ic3A7XHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yjk3OCBuLTIgXHViM2NjXHVjNzQwIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyOTQgXHViM2NjXHVjNzc0XHViMmU0LiZuYnNwO1x1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0Jm5ic3A7XHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0Jm5ic3A7XHVhY2Y1XHViYzMxIFx1ZDU4OVx1Yzc3NCBcdWM3ODhcdWIyZTQuIG5cdWM3NDQgXHVjNzA0XHVkNTVjIFx1YWMxMlx1Yzc3NCZuYnNwO3plcm8gKDApXHVhYzAwIFx1YjQyMCBcdWFjYmRcdWM2YjAgXHVjNzg1XHViODI1XHVjNzQwIFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyZuYnNwOyZxdW90O1NjZW5hcmlvICN4JnF1b3Q7IFx1YmIzOFx1YzdhNVx1YWNmYyZuYnNwOyZxdW90O0Zyb2cgRGlzdGFuY2UgPSZuYnNwO3kmcXVvdDsgXHViYjM4XHVjN2E1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIHhcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWI4NWMgXHViMzAwXHVjY2I0XHViNDFjXHViMmU0ICgxXHViZDgwXHVkMTMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM5YzRcdWIyZTQpLiB5XHViMjk0IFx1YzgwMVx1YzgwOFx1ZDU1YyBcdWMxOGNcdWMyMThcdWM4MTAgXHVjMTRiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWMyZTRcdWMyMThcdWI4NWMgXHViMzAwXHVjY2I0XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWNmMDBcdWM3NzRcdWMyYTRcdWFlNGNcdWM5YzAgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQmbmJzcDtcdWI0YTRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxIFx1ZDU4OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjU5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZyb2dnZXIiLCJkZXNjcmlwdGlvbiI6IlxuXG48cD5cbjxcL3A+PHA+XG5cbkZyZWRkeSBGcm9nIGlzIHNpdHRpbmcgb24gYSBzdG9uZSBpbiB0aGUgbWlkZGxlIG9mIGEgbGFrZS4gU3VkZGVubHkgaGVcbm5vdGljZXMgRmlvbmEgRnJvZyB3aG8gaXMgc2l0dGluZyBvbiBhbm90aGVyIHN0b25lLiBIZSBwbGFucyB0byB2aXNpdCBoZXIsXG5idXQgc2luY2UgdGhlIHdhdGVyIGlzIGRpcnR5IGFuZCBmdWxsIG9mIHRvdXJpc3RzJyBzdW5zY3JlZW4sIGhlIHdhbnRzIHRvXG5hdm9pZCBzd2ltbWluZyBhbmQgaW5zdGVhZCByZWFjaCBoZXIgYnkganVtcGluZy5cbjxcL3A+PHA+XG5VbmZvcnR1bmF0ZWx5IEZpb25hJ3Mgc3RvbmUgaXMgb3V0IG9mIGhpcyBqdW1wIHJhbmdlLiBUaGVyZWZvcmUgRnJlZGR5XG5jb25zaWRlcnMgdG8gdXNlIG90aGVyIHN0b25lcyBhcyBpbnRlcm1lZGlhdGUgc3RvcHMgYW5kIHJlYWNoIGhlciBieVxuYSBzZXF1ZW5jZSBvZiBzZXZlcmFsIHNtYWxsIGp1bXBzLlxuPFwvcD48cD5cblRvIGV4ZWN1dGUgYSBnaXZlbiBzZXF1ZW5jZSBvZiBqdW1wcywgYSBmcm9nJ3MganVtcCByYW5nZSBvYnZpb3VzbHkgbXVzdCBiZSBhdFxubGVhc3QgYXMgbG9uZyBhcyB0aGUgbG9uZ2VzdCBqdW1wIG9jY3VyaW5nIGluIHRoZSBzZXF1ZW5jZS5cbjxcL3A+PHA+XG5UaGUgPGk+ZnJvZyBkaXN0YW5jZTxcL2k+IChodW1hbnMgYWxzbyBjYWxsIGl0IDxpPm1pbmltYXggZGlzdGFuY2U8XC9pPilcbmJldHdlZW4gdHdvIHN0b25lcyB0aGVyZWZvcmUgaXMgZGVmaW5lZCBhcyB0aGUgbWluaW11bSBuZWNlc3Nhcnlcbmp1bXAgcmFuZ2Ugb3ZlciBhbGwgcG9zc2libGUgcGF0aHMgYmV0d2VlbiB0aGUgdHdvIHN0b25lcy4gXG48XC9wPjxwPlxuWW91IGFyZSBnaXZlbiB0aGUgY29vcmRpbmF0ZXMgb2YgRnJlZGR5J3Mgc3RvbmUsIEZpb25hJ3Mgc3RvbmUgYW5kIGFsbFxub3RoZXIgc3RvbmVzIGluIHRoZSBsYWtlLiBZb3VyIGpvYiBpcyB0byBjb21wdXRlIHRoZSA8aT5mcm9nIGRpc3RhbmNlPFwvaT5cbmJldHdlZW4gRnJlZGR5J3MgYW5kIEZpb25hJ3Mgc3RvbmUuXG5cbjxcL3A+IiwiaW5wdXQiOiJcblxuVGhlIGlucHV0IGZpbGUgd2lsbCBjb250YWluIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIFxuVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb250YWluIHRoZSBudW1iZXIgb2Ygc3RvbmVzIDxpPm48XC9pPlxuKDJubiBsaW5lcyBlYWNoIGNvbnRhaW4gdHdvIGludGVnZXJzXG54PHN1Yj5pPFwvc3ViPix5PHN1Yj5pPFwvc3ViPlxuKDAgaSx5PHN1Yj5pPFwvc3ViPiBpLlxuU3RvbmUgIzEgaXMgRnJlZGR5J3Mgc3RvbmUsIHN0b25lICMyIGlzIEZpb25hJ3Mgc3RvbmUsIHRoZSBvdGhlciA8aT5uPFwvaT4tMlxuc3RvbmVzIGFyZSB1bm9jY3VwaWVkLlxuVGhlcmUncyBhIGJsYW5rIGxpbmUgZm9sbG93aW5nIGVhY2ggdGVzdCBjYXNlLlxuSW5wdXQgaXMgdGVybWluYXRlZCBieSBhIHZhbHVlIG9mIHplcm8gKDApIGZvciA8aT5uPFwvaT4uXG5cbiIsIm91dHB1dCI6IlxuXG5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgbGluZSBzYXlpbmcgXCJTY2VuYXJpbyAjPGk+eDxcL2k+XCIgYW5kIGEgbGluZVxuc2F5aW5nIFwiRnJvZyBEaXN0YW5jZSA9IDxpPnk8XC9pPlwiIHdoZXJlIDxpPng8XC9pPiBpcyByZXBsYWNlZCBieSB0aGUgdGVzdFxuY2FzZSBudW1iZXIgKHRoZXkgYXJlIG51bWJlcmVkIGZyb20gMSkgYW5kIDxpPnk8XC9pPiBpcyByZXBsYWNlZCBieSB0aGVcbmFwcHJvcHJpYXRlIHJlYWwgbnVtYmVyLCBwcmludGVkIHRvIHRocmVlIGRlY2ltYWxzLlxuUHV0IGEgYmxhbmsgbGluZSBhZnRlciBlYWNoIHRlc3QgY2FzZSwgZXZlbiBhZnRlciB0aGUgbGFzdCBvbmUuXG5cbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==