المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۶:سوال ۱۳

Polystack

ﺩﺭ ﺁﺳ‰ﺘ‰ﺎﻧ‰ﻪﯼ ﻧ‰ﻤ‰ﺎﯾ‰ﺸ‰ﮕ‰ﺎﻩ ﮐ‰ﺘ‰ﺎﺏ ﻗ‰ﺮﺍﺭ ﺍﺳ‰ﺖ ﺗ‰ﻌ‰ﺪﺍﺩﯼ ﺍﺯ ﻧ‰ﻘ‰ﺎﺷ‰ﯽﻫ‰ﺎﯼ ﻧ‰ﻤ‰ﻮﻧ‰ﻪﯼ ﮐ‰ﻮﺩﮐ‰ﺎﻥ ﺭﻭﯼ ﯾ‰ﮏ ﺳﺎﺧﺘﻤﺎﻥ ﺑﻠﻨﺪ ﻧﺼﺐ ﺷﻮﺩ. ﺑﺮﺍﯼ ﻧﺼﺐ ﺍﯾﻦ ﻧﻘﺎﺷﯽﻫﺎ ﯾﮏ ﻧﺮﺩﺑﺎﻥ ﺍﺣﺘﯿﺎﺝ ﺩﺍﺭﯾﻢ ﻭ ﺑﺮﺍﯼ ﺍﺭﺯﺍﻥ ﺩﺭﺁﻣﺪﻥ ﺁﻥ ﻣ‰ﯽﺧ‰ﻮﺍﻫ‰ﯿ‰ﻢ ﻧ‰ﻘ‰ﺎﺷ‰ﯽﻫ‰ﺎ ﺭﺍ ﻃ‰ﻮﺭﯼ ﺭﻭﯼ ﺍﯾ‰ﻦ ﺳ‰ﺎﺧ‰ﺘ‰ﻤ‰ﺎﻥ ﻗ‰ﺮﺍﺭ ﺩﻫ‰ﯿ‰ﻢ ﮐ‰ﻪ ﺍﺭﺗ‰ﻔ‰ﺎﻉ ﺑ‰ﺎﻻﺗ‰ﺮﯾ‰ﻦ ﻧ‰ﻘ‰ﻄ‰ﻪﯼ ﮐ‰ﻞ ﻧﻘﺎﺷﯽﻫﺎ ﮐﻤﯿﻨﻪ ﺷﻮﺩ. ﻫﺮ ﻧﻘﺎﺷﯽ ﺑﻪ ﺷﮑﻞ ﯾﮏ ﭼﻨﺪﺿﻠﻌﯽ ﻣﺤﺪﺏ ﺍﺳﺖ. ﻧﻘﺎﺷﯽﻫﺎ ﻧﺒﺎﯾﺪ ﻫﻢﭘﻮﺷﺎﻧﯽ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻨﺪ ﻭ ﻧﻤﯽﺗﻮﺍﻥ ﺁﻥﻫﺎ ﺭﺍ ﭼﺮﺧﺎﻧﺪ.

ﺍﯾﻦ ﯾﮏ ﻣﺴﺌﻠﻪﯼ خروجی تنها می‌باشد. برای ﺷﻤﺎ ﺗﻌﺪﺍﺩﯼ ﻓﺎﯾﻞ ﻭﺭﻭﺩﯼ ﺁﻣﺎﺩﻩ ﺷﺪﻩ ﺍﺳﺖ ﮐﻪ ﺑﺎﯾﺪ ﻓﺎﯾﻞﻫﺎﯼ ﺧﺮﻭﺟﯽ ﻣﺘﻨﺎﻇﺮﺷﺎﻥ ﺭﺍ ﺳﺎﺧﺘﻪ ﻭ ﺍﺭﺳﺎﻝ ﮐﻨﯿﺪ. ﻓﺎﯾﻞﻫﺎﯼ ﻭﺭﻭﺩﯼ ﺑﺎ ﻧﺎﻡﻫﺎﯼ $polystack1.in$، $polystack2.in$، … و $polystack12.in$ به صورت فشرده ($zip$) در قسمت $Download$ در واسط مسابقات قرار دارند . شما باید فایل‌های خروجی $polystack1.out$، $polystack2.out$، … و $polystack12.out$ را ساخته، ﺩﺭ ﯾﮏ ﭘﻮﺷﻪ ﻗﺮﺍﺭ ﺩﻫﯿﺪ ﻭ ﭘﺲ ﺍﺯ ﻓﺸﺮﺩﻩﺳﺎﺯﯼ (با $zip$ یا $gzip$) برای ارزش‌یابی ارسال کنید. لازم نیست که همه‌ی خروجی‌ها را در آرشیو ارسالی خود قرار دهید، ﻭ ﺍﮔ‰ﺮ ﻧ‰ﺘ‰ﻮﺍﻧ‰ﺴ‰ﺘ‰ﯿ‰ﺪ ﺑ‰ﺮﺧ‰ﯽ ﺍﺯ ﻣ‰ﻮﺍﺭﺩ ﺭﺍ ﺣ‰ﻞ ﮐ‰ﻨ‰ﯿ‰ﺪ، ﮐ‰ﺎﻓ‰ﯽ ﺍﺳ‰ﺖ ﻣ‰ﻮﺍﺭﺩﯼ ﺭﺍ ﮐ‰ﻪ ﺣ‰ﻞ ﻧ‰ﻤ‰ﻮﺩﻩﺍﯾ‰ﺪ، ﺩﺭ ﺁﺭﺷ‰ﯿ‰ﻮ ﺍﺭﺳﺎﻟﯽ ﺟﺎﯼ ﺩﻫﯿﺪ. ﺍﻧﺪﺍﺯﻩﯼ ﺁﺭﺷﯿﻮ ﺍﺭﺳﺎﻟﯽ ﻧﻤﯽﺗﻮﺍﻧﺪ ﺑﯿﺶ ﺍﺯ ۱۰۰ ﮐﯿﻠﻮﺑﺎﯾﺖ ﺑﺎﺷﺪ.

ورودی

در سطر اول ورودی، $n$، تعداد نقاشی‌ها و $w$ عرض ساختمان‌ آمده است.

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

اول از همه، $m_i$ تعداد رئوس چندضلعی $i$ام و بعد از آن، $m_i$ جفت عدد به عنوان مختصات رئوس این چند ضلعی آمده است. رئوس چند ضلعی ممکن است به ترتیب ساعت‌گرد یا پاد‌ساعت‌گرد در ورودی آمده باشند. عرض ساختمان و مختصات رئوس چندضلعی، همگی اعدادی اعشاری هستند. دقت کنید که مختصه‌ی $x$ لبه‌ی سمت چپ دیوار ۰ و مختصه‌ی $x$ لبه‌ی سمت راست آن $w$ است. در ضمن مختصه‌ی $y$ زمین هم ۰ است.

خروجی

در سطر اول فایل خروجی، $h$، ارتفاعی که هیچ نقاشی در چیدمان خود از آن بالاتر نیسیت را بنویسید.

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

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

این شکل نمونه‌ی ورودی را نشان می‌دهد:

ورودی نمونه خروجی نمونه
3 3.0
3
0 0
1 0
2 2
4
0 0
1 0
1 1.5
0 1
4
0 1
0 0
1 0
2 1
2
0.5 0
2 0
0 1.5

ابزار صفحه