المپدیا

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

ابزار کاربر

ابزار سایت


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

مستطیل‌های رنگی

$N$ مستطیل با رنگ‌های مختلف بر روی یک صفحه کاغذ سفید به‌ترتیب قرار داده می‌شوند. ابعاد کاغذ سفید $a$ سانتی‌متر در جهت محور $x$ و $b$ سانتی‌متر در جهت محور $y$ است. مستطیل‌ها را طوری روی صفحه‌ی کاغذ قرار می‌دهیم که اضلاع آن‌ها با لبه‌ی کاغذ موازی باشند و کلیه مستطیل‌ها در داخل صفحه قرار بگیرند. در نتیجه این کار «اشکالی» با رنگ‌های مختلف ایجاد می‌شوند. دو ناحیه‌ی هم‌رنگ را بخشی از یک «شکل» می‌گیریم اگر حداقل در یک نقطه (مثلا در یک راس) با هم مشترک باشند. در غیر این صورت، این دو ناحیه شکل‌های متفاوت هستند. مسئله این است که مساحت هر یک از این شکل‌ها را پیدا کنیم. $a$ و $b$ اعداد صحیح و مثبت و زوج هستند و از ۳۰ بزرگ‌تر نیستند. مبدا مختصات مورد استفاده در مرکز صفحه کاغذ قرار دارد و محورهای مختصات را موازی با لبه‌های کاغذ می‌گیریم.

ورودی

داده‌های ورودی مختلف در یک فایل به صورت زیر نوشته شده‌اند:

  • $a$، $b$ و $N$ در سطر اول هر مجموعه از داده با حداقل یک فاصله خالی بین آن‌ها قرار دارند.
  • در هر سطر از $N$ سطر بعد مقادیر زیر وجود دارند:

– مختصات راس سمت چپ و پایین یک مستطیل و پس از آن مختصات راس بالا و سمت راست آن مستطیل. مختصات همگی اعداد صحیح هستند.

– سپس رنگ مستطیل که عدد صحیح بین ۱و ۶۴ است. عدد ۱ مربوط به رنگ سفید است.

مستطیل‌ها به همان ترتیبی که در فایل ورودی آمده‌اند بر روی کاغذ، یکی بعد از دیگری، قرار می‌گیرند و ممکن است یک مستطیل قسمتی و یا تمام مستطیل دیگری را بپوشاند. مجموعه داده‌های مختلف با یک سطر خالی از هم جدا شده‌اند.

برنامه‌ای بنویسید که مجموعه داده بعدی را از فایل ورودی بخواند. مساحت هر شکل رنگی را محاسبه کند. توجه کنید که شکل فیلد از خود صفحه کاغذ و از مستطیل‌های سفید رنگ ایجاد می‌شود.

خروجی

در فایل خروجی رنگ و ماسحت هر شکل را بنویسید. این اطلاعات باید به صورت صعودی و بر حسب رنگ اشکال مرتب باشد.

خروجی‌های مربوط به ورودی‌های مختلف باید با یک سطر فاصله از هم جدا شوند.

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

ورودي نمونه خروجي نمونه
20 12 5
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1

30 30 2
0 0 5 14 2
-10 -7 0 13 15
1 172
2 47
4 12
4 8
12 1

1 630
2 70
15 200

ابزار صفحه