غوغای ستارگان


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

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

او گفت که می‌تواند تعدادی ستاره به Quera بدهد که دیگر نیازی به برگزاری مسابقه نباشد و Quera نیز طبعاً از این پیشنهاد بسیار استقبال کرد!

پس از گذشت روزها، بالاخره این دوست ستاره‌ها را برای Quera فرستاد، اما این ستارگان با آنچه Quera انتظار داشت بسیار متفاوت بودند. او تعدادی عکس از ستارگان برای Quera‌ فرستاده بود! Quera پس از این اتفاق، خونسردی خود را حفظ کرد و تلاش کرد تهدیدها را تبدیل به فرصت‌ها کند؛ پس چالشی از روی این‌ها برای شما پدید آورد!

شما باید برنامه‌ای بنویسید که با ورودی گرفتن این عکس‌ها، ستاره‌های داخل آن‌ را بیابد!

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

برنامه‌ی شما باید پس از دریافت عکس (توصیف دقیق فرمت تست‌ها را می‌توانید در بخش "ورودی" بیابید) تعداد ستاره‌هایی که پیدا کرده‌است را چاپ کند و سپس مختصات حداقل یک نقطه از هریک از این ستارگان را در خروجی بنویسد. سپس سیستم تعداد ستاره‌هایی که برنامه‌ی شما یافته‌ را بررسی می‌کند. اگر کمتر از ۷۵٪ تعدادی که برنامه‌ی شما ادعا کرده‌است ستاره شامل نقاط خروجی شما وجود داشت، برنامه‌ی شما نمره‌ی آن تست را دریافت نمی‌کند.

برنامه‌ی شما کافیست ستارگانی را بیابد که با چشم عادی قابل تشخیص و تفکیک از هم هستند. تضمین می‌شود در ورودی‌ها، اندازه‌ی چنین ستارگانی بزرگتر از دیگر ستارگان باشند و در حقیقت تمایز ستارگان کوچکتر از هم با چشم انسان قابل تشخیص نباشد. برای مثال عکس زیر بخشی از یکی از عکس‌های موجود در تست‌ها است: ستاره‌ها ۱

در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید.

یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید: ستاره‌ها ۲

(ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.)

دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد expectedexpected ستاره با این شرایط پیدا کنید و می‌توانید تا 43\frac 4 3 تعداد کل ستارگان با شرایط گفته شده نقطه خروجی دهید. تضمین می‌شود بیش از 54\lceil \frac 5 4 \rceil مقدار expectedexpected در هر تست، ستاره با شرایط گفته شده یافت شود.

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

ورودی🔗

در سطر اول ورودی، سه عدد hh و ww و expectedexpected آمده‌است که به ترتیب نمایانگر مقدار ارتفاع و عرض عکس ورودی و تعداد ستاره‌هایی که باید یافت شوند هستند.

150w,h800150 \le w, h \le 800

سپس در hh سطر بعدی، هر سطر رنگ ww نقطه‌ از تصویر توصیف شده‌است. توصیف هر نقطه بصورت (r, g, b)(r,\ g,\ b) می‌باشد که نمایانگر رنگ این نقطه در صورت نمایش بصورت RGB است. توصیف‌ نقاط با فاصله (space) از هم جدا شده‌اند.

تضمین می‌شود در هریک از تست‌های داده شده، حداکثر ۵۰ ستاره با شرایط گفته شده وجود دارد.

به ورودی‌های نمونه دقت کنید!

خروجی🔗

در سطر اول خروجی یک عدد kk چاپ کنید که نمایانگر تعداد ستاره‌هایی است که در عکس یافت شده‌اند. سپس در هریک از kk سطر بعدی، مختصات یکی از نقاط یکی از ستاره‌های یافت شده را خروجی دهید. هر مختصات باید بصورت (h,w)(h', w') باشد که یعنی این نقطه در سطر hh' توصیف عکس در ورودی سوال، نقطه‌ی ww'امی بوده‌است که توصیف شده‌است.

مثال🔗

ورودی نمونه ۱🔗

ورودی نمونه‌را می‌توانید در اینجا ببینید.

خروجی نمونه ۱🔗

5
13 23
78 139
25 60
67 61
103 130
Plain text

ورودی نمونه ۲🔗

ورودی نمونه‌را می‌توانید در اینجا ببینید.

خروجی نمونه ۲🔗

12
83 160
22 147
88 137
175 229
15 290
144 172
136 119
147 179
47 98
111 97
163 284
154 278
Plain text