المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۹:h

Circle Artwork

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

ورودی

  • ورودی از چند سناریو تشکیل شده است. در خط اول هر سناریو یک عدد $(n ≤ 100)n$آمده است که تعداد نقاط رنگی است.
  • در $n$ خط بعد در خط $i$ ام سه عدد $C_i$ , $Y_i$ , $X_i$ آمده است که $C_i$ رنگ نقطه $i$ ام است و $Y_i$ , $X_i$ مختصات آن نقطه هستند. هر رنگ رشته‌ای است که حداکثر از ۲۰ حرف کوچک انگلیسی تشکیل شده است. مختصات‌ها اعدادی صحیح در بین 1,000,000- و 1,000,000 هستند.
  • خط آخر هر سناریو شامل یک صفر می‌باشد.

خروجی

برای هر سناریو شما باید یک خط چاپ کنید که در آن بیش‌ترین تعداد رنگی که می‌توان برای آن‌ها دایره‌ای با شرایط بالا کشید وجود داشته باشد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
red 1 1
blue 1 2
blue 3 2
yellow 3 3
0
1

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه