- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقای پستچی بترین پستچی دنیاست! در نتیجه او ارتقاء درجه گرفته و باید $k$ پست‌خانه از بین $n$ پست‌خانه‌ی شهر را انتخاب کند و مسئول آن‌ها شود. اگر شهر را از بالا نگاه کنیم مانند صفحه‌ی مختصات دکارتی می‌شود که پست‌خانه‌ی $i$، در نقطه‌ی ($y_i$،$x_i$) است. از آنجایی که آقای پستچی انسان بسیار پرکاری می‌باشند، می‌خواهند جوری پست‌خانه‌ها را انتخاب کنند که مساحت زیر پوشش پست‌خانه‌های انتخابی ایشان بیشینه شود. مساحت زیر پوشش مجموعه‌ای از پست‌خانه‌ها، همان پوش محدب آن‌ها می‌باشد.(برای دریافت اطلاعات بیشتر درباره‌ی پوش محدب به اینجا مراجعه کنید) آقای پستچی می‌خواهد حجم کارش را بداند. از این رو از شما می‌خواهد که به او بگویید این مساحت بیشینه چقدر می‌باشد.
ورودی
در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد پست‌خانه‌های شهر و تعداد پست‌خانه‌هایی است که آقای پستچی انتخاب می‌کند.
سپس در $n$ خط بعدی در خط $i$، به ترتیب $x_i$ و $y_i$ آمده است که نمایانگر مختصات پست‌خانه $i$ می‌باشد. مختصات هیچ پست‌خانه‌ای بیشتر از یک بار نمی‌آید. $$ 3 \le k \le n \le 40 $$ $$ 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
خروجی نمونه
24.0
توضیح: در نمونه‌ی بالا پست‌خانه‌های (۲،۲) ، (۶،۱) ، (۹،۴) و (۳،۷) را انتخاب می‌کنیم که مجموع مساحت زیر پوشش آن‌ها ۲۴ می‌شود.
ارسال پاسخ برای این سؤال