DA-S95-CA2

Time Limit: 1 Second    Memory Limit: 32768 KB

قورباغه گرسنه ای روی سنگی روی برکه نشسته است که ناگهان مگسی را روی یکی دیگر از سنگ های برکه میبیند و قصد میکند تا به سمت او رفته و او را به چنگ آورد. قورباغه میتواند برای طی کردن مسیر بین دو سنگ مستقیما از سنگ اول روی سنگ دوم بپرد یا از تعدادی سنگ میانی استفاده کند. در یک مسیر از سنگ مبدا تا سنگ مقصد, بیشترین فاصله ای که قورباغه از سنگی روی سنگ بعدی پریده را در نظر بگیرید. از آنجا که قورباغه ما خسته است, هدف این است که این فاصله کمینه باشد تا مقدار کمتری بپرد. الگوریتمی طراحی کنید که به قورباغه کمک کرده و بگوید مقدار کمینه این فاصله برای رسیدن به مگس چقدر است.

 

Input

ورودی شامل تعدادی تست کیس است. خط اول هر تست کیس n -تعدادسنگ ها- را نشان میدهد. در n خط بعدی مختصات سنگ های روی برکه به صورت x y داده میشود. مختصات اول مکان قورباغه و مختصات دوم مکان مگس است. همچنین, پایان تست کیس ها با n=0 نشان داده خواهد شد.

Output

Sample Input

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

Sample Output

3.606
2.828

Submit