Processing math: 92%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:عملی نهایی سوم:سوال ۱

points

n‎ نقطه در صفحه‌ی مختصات قرار داده شده‌اند. از شما خواسته می‌شود که با استفاده از حداکثر ‎k‎ نقطه‌ی دیگر، دو نقطه‌ی ‎x‎ و ‎y‎ را به هم ارتباط دهید و در این راه مقدار ‎D‎ را که در ادامه می‌آید کمینه کنید.

دو نقطه‌ی ‎a‎ و ‎b‎ با یکدیگر ارتباط دارند اگر و فقط اگر یکی از دو حالت زیر برقرار باشد: ‎

  • دو دایره به مرکز ‎a‎ و ‎b‎ با شعاع دقیقاً ‎D‎، حداقل در یک نقطه اشتراک داشته باشند.
  • نقطه‌ی ‎c‎ وجود داشته باشد که ‎a‎ و ‎b‎ هر دو با ‎c‎ ارتباط داشته باشند.

شما می‌بایست کمترین مقدار ‎D‎ را به دست آورید که با استفاده از آن و با به کار بردن حداکثر ‎k‎ نقطه‌ی جدید، دو دایره به هم مرتبط شوند.

ورودی

  • در سطر اول ورودی ‎۴‎ عدد ‎n‎، ‎k‎، ‎x‎ و ‎y‎ آمده است. در ‎n‎ سطر بعدی ‎n‎ جفت عدد آمده است که مختصات نقاط را مشخص می‌کنند.
  • 2n1000
  • 0k1000
  • 1 \leq x‎, ‎y \leq n‎, ‎x\neq y
  • قدرمطلق تمامی اعداد ورودی کمتر یا مساوی ‎10^9‎ است‎.‎

خروجی

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

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
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

‎‎


ابزار صفحه