- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شرکتی اتاقی دارد که کف آن به شکل مستطیلی به ابعاد می‌باشد و شرکت می‌خواهد آن را کاشی‌کاری کند. بچه های شرکت کاشی‌های یکسانی به شکل مربع خریده‌اند و باید تمام اتاق را با این کاشی‌ها بپوشانند. برای شروع این پروژه , آن‌ها مراسمی ترتیب دادند و شخص کارشناسی آمد تا کلنگ اولیه را بزند؛ اما چون با این کار زمین اتاق خراب می‌شود به جای اینکار اولین کاشی را در جای دلخواه خود قرار داد و شرکت تصمیم گرفت که تمام کاشی‌های دیگر در این اتاق را طوری بچیند که موازی با این کاشی باشد؛ یعنی ضلع‌های آن‌ها با ضلع‌های این کاشی موازی باشند. همچنین برای محکم شدن کاشی‌ها باید شرط زیر برقرار شود:
هر ضلع از هر کاشی باید حداکثر با یک کاشی دیگر مجاورت داشته باشد؛ یعنی مثلا حالت زیر برای کاشی‌ها قابل قبول نیست:
در حالی که حالت زیر قابل قبول است:
نکته‌ای که در این کاشی‌کاری وجود دارد این است که اگر در گوشه‌های مستطیل مثلا لازم بود که یک تکه‌ای از یک کاشی استفاده شود، بقیه این کاشی دور ریخته‌خواهد شد؛ یعنی برای پوشاندن آن گوشه یک کاشی کامل مصرف می‌شود. (برای فهم بیشتر به نمونه‌ها و شکل‌های مربوطه توجه کنید.)
حال از شما میخواهیم حداقل تعداد کاشی‌های لازم را حساب کنید.
** دقت کنید که تنها کاشی‌هایی را بشمارید که یک ناحیه‌ی ناتهی از اتاق (مستطیل) را می‌پوشانند. (اشتراک خط یا نقطه تهی حساب می‌شود.) **
ورودی
در سطر اول ورودی دو عدد و آمده است که به ترتیب نمایانگر طول و عرض کف اتاق می‌باشد.
سپس در سه سطر، در هر سطر مختصات دکارتی یک گوشه از کاشی اولیه داده می‌شود. نحوه‌ی دادن مختصات این سه نقطه هم به این صورت است که نقطه‌ی پایین چپ مستطیل را نقطه‌ی قرار داده و طول و عرض مستطیل را به ترتیب محور و صفحه مختصات دکارتی در نظر می‌گیریم. حال در این صفحه‌ی مختصات، مختصات سه گوشه‌ی کاشی اولیه را می‌دهیم.
تمام مختصات‌های ورودی و ابعاد مستطیل صحیح می‌باشد. تضمین می‌شود که کاشی اولیه به طور کامل در داخل مستطیل جا می‌شود؛ یعنی حتی با اضلاع مستطیل هم برخورد نمی‌کند.
خروجی
در تنها سطر خروجی تعداد مربع‌های لازم برای پوشاندن کل اتاق را خروجی دهید.
مثال
ورودی نمونه ۱
خروجی نمونه ۱
توضیحات نمونه‌ی اول:
کاشی‌ها با رنگ زرد مشخص شده است.
ورودی نمونه ۲
خروجی نمونه ۲
توضیحات نمونه‌ی دوم:
ارسال پاسخ برای این سؤال