همان‌طور که از امتحانات تئوری به یاد دارید، سیمرغ قول داده بود که اگر شایان‌خان آن دو سوال تئوری را حل کند، شایان‌خان را به هر آن‌چه که می‌خواهد برساند. پس از آن‌که شایان‌خان سوال‌ها را حل کرد، سیمرغ از او پرسید که چه آرزویی دارد؟ از آن‌جا که سیمرغ سوالات خیلی سختی به شایان‌خان داده بود، شایان‌خان گفت : «آرزو می‌کنم تمام پرهای سیمرغ بریزد!» سیمرغ با شنیدن این جمله بسیار ترسید و به شایان‌خان گفت که به جای آن‌که پرهای او را بریزاند، او هم یک سوال به سیمرغ بدهد و آرزوی دیگری کند. شایان‌خان هم تصمیم گرفت که یک سوال الگوریتمی به سیمرغ بدهد.

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

1. رئوس پوش محدب از نقاط سفید باشند.
2. هیچ نقطه‌ی سیاهی درون یا روی ضلع‌های پوش محدب قرار نداشته باشد.

الگوریتمی با پیچیدگی زمان اجرای $O(n^5)$ ارائه دهید که بزرگ‌ترین پوش محدب با خواص بالا را جواب بدهد تا از ریختن پرهای سیمرغ جلوگیری کنید (در صورتی که الگوریتمی با پیچیدگی زمان اجرای چندجمله‌ای با درجه‌ی بالاتر ارائه دهید، بخشی از نمره به شما تعلق خواهد گرفت).

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