المپدیا

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

ابزار کاربر

ابزار سایت


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

Africa

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

رئیس آدم‌های خبیث، یک نقشه داشت. یک روز روی آن تعدادی چندضلعی کشید. بعد دید که نقشه به تعدادی ناحیه تقسیم شده. با خباثت زیاد و دوز و کلک مردم هر ناحیه را باهم متحد کرد و یک قبیله از آن‌ها ساخت و بعد قبیله‌ها را به جان هم انداخت!

البته واضح است که دو قبیله‌ای که قلمرو‌شان مرز مشترکی ندارد نمی‌توانند به جان هم بیفتند. از طرفی به خاطر خباثت زیاد رئیس، هر دو قبیله‌ای که قلمروشان مرز مشترک داشت به جان هم افتادند.

مدت‌ها گذشت تا بالاخره کامپیوترها اختراع شدند و سر و کله‌ی آدم‌های خوب پیدا شد. رئيس آدم‌های خوب می‌خواهد قبایل آفریقا را باهم آشتی دهد. برای این‌کار تصمیم دارد یک مهمانی آشتی‌کنان برگزار کند و تعدادی از آدم‌های مهم آفریقا را در آن دعوت کند. منتها چون آدم‌هایی که قبیله‌شان در جنگ هستند چشم دیدن هم‌دیگر را ندارند، نباید در این مهمانی باهم حاضر شوند.

شما به عنوان یک آدم خوب قصد دارید به رئیس تا بتواند بیش‌ترین تعداد ممکن، آدم مهم را دعوت کند. کامپیوتر هم که اختراع شده. پس منتظر چه هستید؟

شکل روبه‌رو، متعلق به ورودی نمونه است. در این شکل آدم خبیث ۲ مستطیل کشیده و آفریقا به ۳ ناحیه تقسیم شده. در هر یک از این ناحیه‌ها ۱ آدم مهم زندگی می‌کند. آدم وسطی با هر یک از آدم‌های دیگر نمی‌تواند در مهمانی حاضر شود. پس بهترین حالت دعوت کردن دو آدم دیگر است.

برنامه‌ای بنویسید که:

  • مشخصات آفریقا و آدم‌های مهم را از ورودی بخواند.
  • بیش‌ترین تعداد آدم‌های ممکن را که می‌توان به مهمانی دعوت کرد حساب کند.
  • نتیجه را در خروجی بنوسد.

ورودی

در سطر اول ورودی، به ترتیب دو عدد $n$(تعداد چندضلعی‌ها) و $m$(تعداد آدم‌های مهم) قرار دارد.($1\leq n \leq 10$ و $1\leq m \leq 100$)

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

ابتدا $p$(تعداد رئوس چندضلعی) و سپس $p$ جفت عدد حقیقی که مختصات رئوس، به ترتیب پیمایش چندضلعی، هستند.($3\leq p \leq 10$)

در هر یک از $m$ سطر بعد، یک جفت عدد حقیقی آمده که مختصات محل زندگی یک آدم مهم را نشان می‌دهد.

قدر مطلق اعداد حقیقی ورودی از ۱۰۰۰ بیش‌تر نمی‌شود و حداکثر با سه رقم بعد از اعشار داده می‌شوند.

هیچ سه ضلعی (از چندضلعی‌های یکسان یا مختلف) از یک نقطه نمی‌گذرند.

هیچ دو ضلعی (از چندضلعی‌های یکسان یا مختلف) در بیش از یک نقطه اشتراک ندارند.

هیچ راسی از یک چندضلعی روی محیط چندضلعی دیگر قرار ندارد.

هر آدم مهم، درون حداقل یکی از چندضلعی‌ها قرار دارد ولی روی محیط هیچ‌یک از چندضلعی‌ها نیست.

چندضلعی‌ها ممکن است هم‌دیگر را قطع کنند، ولی هیچ چندضلعی خودش را قطع نمی‌کند.

خروجی

در تنها سطر خروجی حداکثر تعداد آدم‌هایی که می‌توان به مهمانی دعوت کرد را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2 3
4 0.0 0.0 3.0 0.0 3.0 3.0 0.0 3.0
4 1.0 1.0 4.0 1.0 4.0 4.0 1.0 4.0
0.5 0.5
2.0 2.0
3.5 3.5
2

ابزار صفحه