انتخاب پست‌خانه


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

آقای پستچی بترین پستچی دنیاست! در نتیجه او ارتقاء درجه گرفته و باید kk پست‌خانه‌ از بین nn پست‌خانه‌ی شهر را انتخاب کند و مسئول آن‌ها شود. اگر شهر را از بالا نگاه کنیم مانند صفحه‌ی مختصات دکارتی می‌شود که پست‌خانه‌ی ii، در نقطه‌ی (yiy_i،xix_i) است. از آنجایی که آقای پستچی انسان بسیار پرکاری می‌باشند، می‌خواهند جوری پست‌خانه‌ها را انتخاب کنند که مساحت زیر پوشش پست‌خانه‌های انتخابی ایشان بیشینه شود. مساحت زیر پوشش مجموعه‌ای از پست‌خانه‌ها، همان پوش محدب آن‌ها می‌باشد.(برای دریافت اطلاعات بیشتر درباره‌ی پوش محدب به اینجا مراجعه کنید) آقای پستچی می‌خواهد حجم کارش را بداند. از این رو از شما می‌خواهد که به او بگویید این مساحت بیشینه چقدر می‌باشد.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد nn و kk آمده است که به ترتیب نمایانگر تعداد پست‌خانه‌های شهر و تعداد پست‌خانه‌هایی است که آقای پستچی انتخاب می‌کند.

سپس در nn خط بعدی در خط ii، به ترتیب xix_i و yiy_i آمده است که نمایانگر مختصات پست‌خانه ii می‌باشد. مختصات هیچ پست‌خانه‌ای بیشتر از یک بار نمی‌آید. 3kn40 3 \le k \le n \le 40 0xi,yi1 000 0 \le x_i , y_i \le 1\ 000

خروجی🔗

در تنها سطر خروجی باید جواب را با دقیقا یک رقم اعشار خروجی دهید.

مثال🔗

ورودی نمونه🔗

7 4
2 2
1 5
6 1
5 5
3 7
7 6
9 4
Plain text

خروجی نمونه🔗

24.0
Plain text

توضیح: در نمونه‌ی بالا پست‌خانه‌های (۲،۲) ، (۶،۱) ، (۹،۴) و (۳،۷) را انتخاب می‌کنیم که مجموع مساحت زیر پوشش آن‌ها ۲۴ می‌شود.

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