Triangles

یک مثلث ‎شیطانی‎ مثلثی است که مختصات رئوس آن به صورت ‎$(x-3\times k,y)$‎ ،‎‌$(x+3\times k,y)$‎ و ‎$(x,y+4 \times k)$‎ که ‎$k$‎ عددی حقیقی و مثبت است هستند‎. ‎ به شما مختصات ‎$n$‎ مثلث شیطانی داده شده است، شما باید کوچک‌ترین مثلث شیطانی را بیابید که حداقل ‎$m$‎ تا از مثلث های داده شده در آن قرار بگیرند‎. ‎

• در سطر اول ورودی دو عدد ‎$n$‎ و ‎$m$‎ آمده است‎.‎
• در هر یک از ‎$n$‎ سطر بعدی ‎۳ عدد ‎$x_i$‎ و ‎$y_i$‎ و ‎$k_i$‎ آمده است که یک مثلث شیطانی را مشخص می‌کند. تمام اعداد ورودی طبیعی هستند.
• ‎ $1 \leq m < n \leq 3000$‎
• ‎ $0 \leq x_i,y_i,k_i \leq 10^7$‎
• ‎‎ در حداقل ‎۳۰‎ درصد تست ها ‎$n$‎ کمتر یا مساوی ‎۱۰۰‎ است

فرض کنید مساحت کوچکترین مثلث شیطانی که حداقل ‎$m$‎ مثلث را دربر دارد برابر با ‎$12.r^2$‎ باشد. در تنها سطر خروجی عدد ‎$r$‎ را با دقیقاْ دو رقم اعشار چاپ کنید. ‎ برای چاپ کردن عدد با دقیقاْ دو رقم اعشار می توانید از دستورات زیر استفاده کنید:

‎cout<<fixed;
‎cout.precision(2);
‎cout<<result<<endl;‎

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

شکل زیر وضعیت مثلث‌های شیطانی را نمایش می‌دهد. مثلث بهینه‌ای که حداقل ‎۳‎ مثلث درون آن قرار می‌گیرند در شکل با رنگ قرمز نشان داده شده است. ‎

• سوال بعد
• سوال قبل