Antena

‎$n$‎ مرکز اطلاعاتی در یک منطقه نظامی قرار دارند. این مراکز برای این که بتوانند کار خود را به صورت دقیق انجام دهند باید به شبکه اینترانت منطقه متصل باشند. برای همین می‌خواهیم ‎$k$‎ آنتن اینترانت را در نقاطی از این منطقه قرار دهیم به طوری که هر مرکز حداقل توسط یک آنتن پوشش داده شود. می توانید فرض کنید که منطقه به صورت یک صفحه دو بعدی است که مراکز اطلاعاتی و آنتن‌ها به صورت نقطه در آن قرار دارند و هر آنتن، اینترانت را در یک دایره به مرکز خود و شعاع مشخص سرویس دهی می‌کند. ‎ می‌دانیم که آنتن‌ها فقط می‌توانند بر روی خط ‎$y = 0$‎ قرار داده شوند و همچنین شعاع سرویس دهی تمامی آنتن‌ها باید برابر با هم باشد. از آنجایی که می‌خواهیم هزینه کمی برای نصب آنتن‌ها پرداخت کنیم، می‌خواهیم کمترین ‎$R$‎ را پیدا کنیم که بتوان با قرار دادن ‎$k$‎ آنتن به شعاع سرویس دهی ‎$R$‎ بر روی خط ‎$y = 0$‎ همه مراکز اطلاعاتی را پوشش داد.

شما باید برنامه‌ای بنویسید که با گرفتن اطلاعات مربوط به سوال مقدار کمینه ‎$R$‎ را به دست آورد.

• در سطر اول ورودی دو عدد $(1 \leq n \leq 200000)$‎ و $(1 \leq k \leq 200000)$‎ به ترتیب نشان‌دهنده تعداد مراکز اطلاعاتی و تعداد آنتن‌ها آمده است.‎
• در ‎$n$‎ سطر بعدی در هر سطر دو عدد ‎$(-10^6 \leq x_i \leq 10^6)$‎ و ‎$(-10^6 \leq y_i \leq 10^6)$‎ به ترتیب آمده است که مختصات مراکز اطلاعاتی را مشخص می‌کنند.‎
• تمام اعداد ورودی صحیح می‌باشند.

در تنها سطر خروجی پاسخ سوال را با دقیقاً سه رقم اعشار چاپ کنید. می توانید از قطعه برنامه زیر برای چاپ کردن خروجی کمک بگیرید:‎

‎

‎cout<<fixed;
‎cout.precision(3);‎
‎cout<<result<<endl;‎

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل