$n$ نقطه در صفحه‌ی مختصات قرار داده شده‌اند. از شما خواسته می‌شود که با استفاده از حداکثر $k$ نقطه‌ی دیگر، دو نقطه‌ی $x$ و $y$ را به هم ارتباط دهید و در این راه مقدار $D$ را که در ادامه می‌آید کمینه کنید.
دو نقطه‌ی $a$ و $b$ با یکدیگر ارتباط دارند اگر و فقط اگر یکی از دو حالت زیر برقرار باشد:
شما می‌بایست کمترین مقدار $D$ را به دست آورید که با استفاده از آن و با به کار بردن حداکثر $k$ نقطه‌ی جدید، دو دایره به هم مرتبط شوند.
در تنها سطر خروجی پاسخ سوال را با دقیقاً ۳ رقم اعشار چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 4 1 1 3 1 0 0 1 -1 0 0 -1 | 1.000 |
| 5 1 1 5 10 0 20 0 30 0 40 0 50 0 | 10.000 |