- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۶۴ مگابایت
مرکز سورتینگ دیجیکالا دارای مجموعه‌ای از نقاله‌ها برای سورت اتوماتیک بسته‌ها است. هر کدام از این نقاله‌ها از تعدادی استوانه‌ی چرخنده یا رولر مجاور هم تشکیل شده‌اند به نحوی که هر رولر می‌تواند یک بسته را به رولرهای سمت راست، چپ، جلو و عقب خود منتقل کند. توجه داشته باشید که ممکن است یک نقاله شامل یک تک رولر باشد. هر نقاله یک نقطه‌ی شروع و یک نقطه‌ی پایان دارد. هر دو رولر که از یک سمت با هم مجاور باشند، عضو یک نقاله هستند.
برای کنترل آلودگی صوتی مرکز سورتینگ تصمیم گرفته شد هر نقاله توسط یک و فقط یک کیوسک عایق صدا احاطه شود.
کیوسک‌ها به صورت مکعب مستطیل‌هایی هستند که بر روی نقاله‌ها قرار می‌گیرند و هزینه‌ی هر کیوسک بر اساس مساحت سطح مقطع آن حساب می‌شود و مرکز سورتینگ تمایل دارد کمترین هزینه را برای خرید این کیوسک‌ها داشته باشد.
شکل زیر نمای بالا از یکی از مراکز سورتینگ دیجیکالا است. خانه‌های آبی رنگ نشان‌دهنده‌ی رولرهای نقاله‌ها و خط‌های قرمز نشان‌دهنده‌ی محیط کیوسک‌های قرار گرفته در اطراف هر نقاله است.
الگوریتمی طراحی کنید که با داشتن محل رولرها، مساحت بزرگترین کیوسک لازم را محاسبه کند.
ورودی
در خط اول طول $n$ و عرض $m$ مرکز سورتینگ و $k$ تعداد نقاله‌ها داده می‌شوند. $$1 \leq m, n \leq 500$$
در $k$ خط بعدی هر خط $r$ شماره‌ی ردیف در سورتینگ سنتر و $c_1$ شماره‌ی ستون آغاز و $c_2$ شماره‌ی ستون پایان یک بخش از نقاله داده می‌شوند.
خروجی
مساحت بزرگترین کیوسک
مثال
ورودی نمونه ۱
6 6 7
1 2 4
2 2 3
2 6 6
3 5 5
4 2 2
5 4 6
6 1 4
خروجی نمونه ۱
12
در این نمونه، ورودی و خروجی کاملا مطابق با تصویر صورت سوال است. همانطور که در تصویر مشخص است، بزرگترین مساحت کیوسک برابر ۱۲ است.
ورودی نمونه ۲
4 4 4
1 1 2
2 2 3
3 3 3
4 1 1
خروجی نمونه ۲
9
این نمونه مطابق با تصویر زیر است:
ارسال پاسخ برای این سؤال