- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
روزی از روزها، قرار شد که Quera برای رهنما مسابقاتی برگزار کند و از بین شرکت کنندگان تعدادی ستاره برگزیند و به رهنما معرفی کند. یکی از دوستان Quera با شنیدن چنین خبری سریعا به Quera رفت و پیشنهاد جالبی به آن‌ها داد!
او گفت که می‌تواند تعدادی ستاره به Quera بدهد که دیگر نیازی به برگزاری مسابقه نباشد و Quera نیز طبعاً از این پیشنهاد بسیار استقبال کرد!
پس از گذشت روزها، بالاخره این دوست ستاره‌ها را برای Quera فرستاد، اما این ستارگان با آنچه Quera انتظار داشت بسیار متفاوت بودند. او تعدادی عکس از ستارگان برای Quera فرستاده بود! Quera پس از این اتفاق، خونسردی خود را حفظ کرد و تلاش کرد تهدیدها را تبدیل به فرصت‌ها کند؛ پس چالشی از روی این‌ها برای شما پدید آورد!
شما باید برنامه‌ای بنویسید که با ورودی گرفتن این عکس‌ها، ستاره‌های داخل آن را بیابد!
در تست‌های این سوال ۸ عکس واقعی از آسمان وجود دارد که هرچه شما تعداد بیشتری ستاره بتوانید در این‌ها پیدا کنید، نمره‌ی بیشتری از این سوال می‌گیرید. به این شکل که در ورودی هر تست پیش از توصیف عکس، یک مقدار $expected$ آمده‌است که یعنی اگر شما حداقل به تعداد $expected$ ستاره در عکس بیابید، نمره‌ی تست را دریافت می‌کنید. هر عکس سه بار در تست‌ها آمده‌است که مقدار $expected$ در این سه تست تفاوت دارد.
برنامه‌ی شما باید پس از دریافت عکس (توصیف دقیق فرمت تست‌ها را می‌توانید در بخش "ورودی" بیابید) تعداد ستاره‌هایی که پیدا کرده‌است را چاپ کند و سپس مختصات حداقل یک نقطه از هریک از این ستارگان را در خروجی بنویسد. سپس سیستم تعداد ستاره‌هایی که برنامه‌ی شما یافته را بررسی می‌کند. اگر کمتر از ۷۵٪ تعدادی که برنامه‌ی شما ادعا کرده‌است ستاره شامل نقاط خروجی شما وجود داشت، برنامه‌ی شما نمره‌ی آن تست را دریافت نمی‌کند.
برنامه‌ی شما کافیست ستارگانی را بیابد که با چشم عادی قابل تشخیص و تفکیک از هم هستند. تضمین می‌شود در ورودی‌ها، اندازه‌ی چنین ستارگانی بزرگتر از دیگر ستارگان باشند و در حقیقت تمایز ستارگان کوچکتر از هم با چشم انسان قابل تشخیص نباشد. برای مثال عکس زیر بخشی از یکی از عکس‌های موجود در تست‌ها است:
در این مثال تنها ۵ ستاره وجود دارد که شما باید آن‌ها را بیابید.
یا برای مثال، در عکس زیر (که بازهم بخشی از یکی از عکس‌های تست‌ها است) ۱۲ ستاره وجود دارد که شما باید آن‌ها را بیابید:
(ورودی مثال این دو عکس و یک خروجی معتبرشان در نمونه‌های سوال آمده‌اند.)
دقت کنید که لازم نیست تمام ستارگان با شرایط گفته‌شده را بیابید؛ شما کافیست به تعداد $expected$ ستاره با این شرایط پیدا کنید و می‌توانید تا $\frac 4 3 $ تعداد کل ستارگان با شرایط گفته شده نقطه خروجی دهید. تضمین می‌شود بیش از $\lceil \frac 5 4 \rceil$ مقدار $expected$ در هر تست، ستاره با شرایط گفته شده یافت شود.
جهت تشخیص درست ستاره‌ها، تلاش کنید نقطه‌ای که در ستاره‌ی معرفی شده ارائه می‌دهید در گوشه‌های آن نباشد. (بعنوان مثال، می‌توانید مرکز ثقل شکل ستاره یافت‌شده را خروجی دهید!)
ورودی
در سطر اول ورودی، سه عدد $h$ و $w$ و $expected$ آمده‌است که به ترتیب نمایانگر مقدار ارتفاع و عرض عکس ورودی و تعداد ستاره‌هایی که باید یافت شوند هستند.
$$150 \le w, h \le 800$$
سپس در $h$ سطر بعدی، هر سطر رنگ $w$ نقطه از تصویر توصیف شده‌است. توصیف هر نقطه بصورت $(r,\ g,\ b)$ می‌باشد که نمایانگر رنگ این نقطه در صورت نمایش بصورت RGB است. توصیف نقاط با فاصله (space) از هم جدا شده‌اند.
تضمین می‌شود در هریک از تست‌های داده شده، حداکثر ۵۰ ستاره با شرایط گفته شده وجود دارد.
به ورودی‌های نمونه دقت کنید!
خروجی
در سطر اول خروجی یک عدد $k$ چاپ کنید که نمایانگر تعداد ستاره‌هایی است که در عکس یافت شده‌اند. سپس در هریک از $k$ سطر بعدی، مختصات یکی از نقاط یکی از ستاره‌های یافت شده را خروجی دهید. هر مختصات باید بصورت $(h', w')$ باشد که یعنی این نقطه در سطر $h'$ توصیف عکس در ورودی سوال، نقطه‌ی $w'$امی بوده‌است که توصیف شده‌است.
مثال
ورودی نمونه ۱
ورودی نمونه‌را می‌توانید در اینجا ببینید.
خروجی نمونه ۱
5
13 23
78 139
25 60
67 61
103 130
ورودی نمونه ۲
ورودی نمونه‌را می‌توانید در اینجا ببینید.
خروجی نمونه ۲
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
ارسال پاسخ برای این سؤال