المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۳:سوال ۳

Square Frames

‎ سعید به تازگی وارد خانه جدید خود شده و می‌خواهد آن را تزیین کند. او در نگاه اول متوجه می‌شود که دیوار این خانه دارای تعدادی سوراخ است که باید تا حد ممکن پوشیده شوند. سعید دوست دارد دو تابلو بر روی این دیوار قرار دهد که تعدادی از این سوراخ‌ها را پوشش دهند. بدون هیچ دلیلی شکل هر دو تابلو باید مربع باشد و باز بدون هیچ دلیلی این دو تابلو باید حداقل ‎$k$‎ سوراخ از این دیوار را بپوشانند‎!‎

واضح است که سعید دوست‌ دارد هنگامیکه تابلو‌ها بر روی دیوار نصب می‌شوند ضلع پایینی آن‌ها موازی زمین باشد و هم‌چنین بدیهی است که دو تابلو نمی‌توانند هم‌پوشانی داشته باشند (یعنی باید مساحت اشتراک دو تابلو صفر باشد (تابلو‌‎ها می‌توانند رو ی مرز اشتراک داشته باشند). باز هم بدون هیچ دلیلی سعید می‌خواهد اندازه دو تابلو با هم برابر باشد‎!‎

هدف سعید این است که کمینه اندازه تابلوهایی را پیدا کند که با قرار دادن آن‌ها بتواند ‎$k$‎ تا از سوراخ های دیوار را بپوشاند. دقت کنید که این نقطه‌ها می‌توانند رو مرز تابلوها هم قرار بگیرند. شما باید با گرفتن مختصات سوراخ های دیوار کمترین ‎$\alpha$‎ای را پیدا کنید که بتوان دو تابلوی مربعی موازی محور مختصات با ضلع ‎$\alpha$‎ بر روی دیوار قرار داد که حداقل ‎$k$‎ تا از سوراخ‌های دیوار زیر آن‌ها قرار بگیرند. می‌توانید سوراخ‌ها را به صورت نقطه در نظر بگیرید. ‎

ورودی

  • در سطر اول ورودی دو عدد ‎$n$‎ و ‎$k$‎ نشان دهنده تعداد سوراخ‌ها و حداقل تعداد سوراخ‌هایی که قرار است پوشیده شوند آمده است.
  • در ‎$n$‎ سطر بعدی در هر سطر به ترتیب دو عدد صحیح ‎$x_i$‎ و ‎$y_i$‎ آمده‌اند که مختصات یک سوراخ را نشان می‌دهند.
  • ‎ $1 \leq n \leq 50000$‎.
  • ‎ $3 \leq k \leq n$‎.
  • در ورودی هیچ دو نقطه‌ای روی هم نیستند.
  • ‎ $-2\times10^5 \leq x_i,y_i \leq 2\times10^5$‎.

خروجی

در تنها سطر خروجی کمترین مقدار ‎$\alpha$‎ را برای هر تست چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 500$‎.
  • زیرمسئله‌ی دوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 2500$‎.
  • زیرمسئله‌ی سوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 25000$‎.
  • زیرمسئله‌ی چهارم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 50000$‎.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
9 8‎
0 0‎
0 1‎
1 0‎
1 1‎
10 10‎
10 11‎
11 10‎
11 11‎
100 100
1

توضیحات

در تست نمونه کافیست دو مربع به اندازه ‎۱‎ به رئوس چهار نقطه اول ورودی و چهار نقطه دوم ورودی قرار دهیم. بدیهی است که با مربع‌های کوچک‌تر نمی‌توان این کار را انجام داد.


ابزار صفحه