Wedding Hall

کامران به تازگی یک باغ مستطیل شکل را در قسمت بی‌نظیری در حومه‌ی شهر خریده است. از آن‌جایی که به تازگی این قسمت از حومه‌ی شهر برای برگزاری مراسم عروسی توجه زیادی را به خود جذب کرده است‏، وی تصمیم گرفته است یک مکان برگزاری مراسم عروسی در آن‌جا بسازد. از آن‌جایی که بر طبق مقررات حکومتی قسمت بانوان و آقایان باید‎ جدا باشد‏، وی تصمیم دارد با سه قسمت این مکان را بسازد. ‎‎قسمت بانوان‏، آقایان‏ و مشترک (شامل اتاق استراحت‏، غذاخوری و …). از آن‌جایی که قسمت مشترک باید توسط همگان قابل دسترس باشد‏، تصمیم بر این است که این قسمت وسط باشد. از بین طرح‌های پیشنهادی کامران طرح زیر را پذیرفته است که تمامی قسمت‌ها مربعی شکل و یک اندازه هستند و همانند ‎$ ‎L‎ $‎ به هم وصل شده‌اند. سوال اصلی اینجاست که این مجموعه در کجای باغ باید ساخته شود؟ باغ پر از درختان قدیمی است و به خاطر آلودگی هوا قطع کردن درختان ممنوع است. کامران از شما برای ‎ساخت‎ بزرگ‌ترین مجموعه‌ی ممکن کمک خواسته است.

• سناریوهای مختلفی در ورودی به شما داده می‌شود. در خط اول هر سناریو عدد غیر منفی ‎$(n;1\leq n\leq 50000‎‎) ‎‎‎‎$‎ و دو عدد ‎$ ‎a, ‎b‎ $‎ (کوچک‌تر از ‎$‎1000000‎$‎ ) داده می‌شود.‎$ ‎n‎ $‎ تعداد درختان و ‎$ ‎a‎ $‎ و ‎$ ‎b‎ $‎ طول و عرض باغ هستند. ‎$ ‎[0,a]‎ ‎‎\times ‎[0,b]‎ $‎ بیانگر مدل باغ هستند.
• در هر کدام از ‎$ ‎n‎ $‎ خط بعدی دو عدد صحیح غیر منفی‎$x_i‎‎$‎ و ‎‎$‎y_i‎‎$‎‎ داده شده‌اند‎(‎$0‎<‎ ‎x_i<a‎,0‎<‎‎y_i‎<‎b‎$‎)‎، که مختصات قرارگیری درختان را نشان می‌دهد. می‌توانید مختصات درختان را متمایز فرض کرده‏، همین‌طور طول مستطیل را بر روی محور ‎$ x $‎ها و عرض مستطیل را روی محور ‎$ ‎y‎ $‎ها در نظر بگیرید. ورودی با ‎$ ‎"0 0 0"‎ $‎ خاتمه می‌یابد.

برای هر سناریو مساحت بزرگ‌ترین سالنی را که کامران می‌تواند در باغش بسازد را چاپ نمایید. توجه داشته باشید که درختان و همین‌طور محدوده‌ی باغ می‌توانند با سالن مماس شوند. خروجی را تا دو رقم اعشار رند نمایید.

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

• سوال قبل