====== سوال ۴ ======

اتاقی به شکل یک $n$ ضلعی ساده با اضلاع موازی محورهای مختصات داریم. می خواهیم آن را با تعدادی فرش مستطیل‌شکل بپوشانیم، به طوری که هیچ دوفرشی هم‌پوشانی نداشته باشند و تمام فضای اتاق پوشیده شود.

  - فرض کنید هیچ دونقطه ای هم $x$ یا هم $y$ نیستند، مگراین‌که دو سر یک ضلع باشند. تعداد مستطیل‌های لازم برای پوشاندن اتاق را با فرمولی صریح بر حسب $n$ بدست آورید.
  - الگوریتمی از $O(n^3)$ برای پیداکردن تعداد مستطیل‌های لازم ارائه دهید.
  - حال فرض کنید ممکن است در اتاق ستون هایی به شکل مستطیل با اضلاع موازی محور $x$ و $y$ مختصات داریم، طوری که هیچ کدام از ستون ها با دیواره اتاق برخوردی ندارند.

  * [[سوال ۳|سوال قبل]]