----- برای آگاهی از مسابقات Quera به کانال تلگرام مسابقات بپیوندید. @quera_contests https://telegram.me/quera_contests

پوش مربع


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

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما اکنون با شروع فصل گرما، درگیر نصب سقف برای جلوگیری تابش مستقیم آفتاب روی باغچه‌اش است.

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

محمدرضاص میخواهد آفتابگیرها را با کمترین طول ضلع ممکن بخرد. با ورودی گرفتن مختصات گل‌ها و عدد kk، حداقل طول ضلع آفتابگیرها را خروجی دهید.

ورودی🔗

در سطر اول ورودی دو عدد nn و kk آمده‌اند که به ترتیب نمایانگر تعداد گل‌های باغچه‌ی محمدرضاص و تعداد آفتابگیر‌ها هستند. سپس در هریک از nn سطر بعدی، مختصات یک گل بصورت دو عدد صحیح xi,yix_i, y_i آمده‌ است. (مختصات با فرض اینکه اضلاع باغچه، محورهای مختصات هستند داده شده‌اند.)

1k<n151 \le k < n \le 15

0xi,yi64 0000 \le x_i, y_i \le 64\ 000

خروجی🔗

خروجی باید شامل یک عدد باشد که برابر کمترین طول ممکن برای آفتابگیرهای محمدرضاص است.

مثال🔗

ورودی نمونه🔗

5 2
1 1
2 2
3 3
6 6
7 8
Plain text

خروجی نمونه🔗

2
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.