یک قالب ریخته‌گری دوبُعدی داریم که به شکل مستطیلی است که یک حفره‌ی چندضلعی از آن بُریده‌ایم، و این حفره فقط قسمتی از ضلع بالایی مستطیل را قطع می‌کند (و ضلع دیگری از مستطیل را قطع نمی‌کند). به شکل ‎۱‎ دقت کنید. از بالا آهن مذاب می‌ریزیم تا حفره را پر کند. پس از سرد شدن می‌خواهیم جسم حاصل را از قالب بیرون بکشیم، دقت کنید به دلیل شکل حفره، در آغاز کار فقط ضلع بالایی جسم مجاور هوای آزاد است. در طول بیرون کشیدن، مرز جسم می‌تواند روی مرز قالب بلغزد.

بعضی جهت‌ها هستند که با یک‎ انتقال در آن جهت‌ها شکل بطور کامل از قالب در می‌آید (دوران نداریم). الگوریتمی با زمان چندجمله‌ای بر حسب تعداد رئوس حفره بدهید که همه‌ی این جهت‌ها را مشخص کند. البته ممکن است شکل قالب طوری باشد که چنین جهتی وحود نداشته‌باشد. خروجی الگوریتم می‌تواند تعدادی زاویه‌ی مجاز و تعدادی بازه‌ی زاویه‌ای مجاز باشد‎.

‎ ‎ راهنمایی‎:‎ می‌توان نشان داد که اگر در یک جهت، شکل بتواند کمی حرکت کند بدون این‌که به قالب برخورد کند، آن‌گاه با حرکت در آن جهت می‌توان شکل را بیرون آورد‎.

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