تبلیغات میدانی


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

شرکت SnappSnapp پس از بررسی‌های بسیار تصمیم به برگزاری مسابقه اسنپ چلنج گرفت. با توجه به زمان کمی که برای تبلیغات باقی مانده بود، بلافاصله پارسا تعدادی پوستر مسابقات را درست کرده و برای تبلیغ به دانشگاه خود می‌برد، پوستری که پارسا طراحی کرده‌است به صورت مستطیلی با طول nn و عرض mm است. او پس از رسیدن به دانشگاه به سمت بُرد اصلی رفته تا یکی از پوسترها را آنجا بچسباند. برد اصلی دانشگاه به صورت مستطیلی با طول ww و عرض hh است که kk پوستر تبلیغاتی بر روی آن قرار دارد. هر پوستر تبلیغاتی به صورت مستطیلی است که قسمتی از برد را اشغال کرده است و اضلاعش موازی محور‌های مختصات است.حال پارسا می‌خواهد طوری پوستر خود را روی برد بچسباند که روی هیچ پوستر دیگری قرار نگیرد، همچنین با توجه به اهمیّت مسابقه، پارسا می‌خواهد پوستر در جایی قرار بگیرد که دیده شود! در واقع برای دیده شدن پوستر پارسا می‌خواهد نقطه وسط پوسترش در نزدیک‌ترین جای ممکن به نقطه‌ی وسط برد باشد(فاصله‌ی ۲ نقطه فاصله‌ی اقلیدسی آن‌هاست). به پارسا کمک کنید تا ببیند آیا راهی برای چسباندن پوستر وجود دارد. دقت کنید ممکن است سایر پوسترها روی یک دیگر قرار داشته باشند، اما پارسا نمی‌خواهد پوسترش با هیچ کدام از پوستر‌های موجود روی برد اشتراک داشته باشد.همچنین پارسا برای خوانده شدن پوستر،آن را به همان صورتی که هست می‌چسباند و به هیچ وجه پوستر را دوران نمی‌دهد.

ورودی🔗

در سطر اول ورودی به ترتیب چهار عدد ww و h h و n n و m m و kk است که دو عدد اول ابعاد برد دانشگاه و دو عدد بعدی ابعاد پوستر پارسا‌ است، و عدد آخر تعداد پوستر‌های موجود روی برد است. تضمین می‌شود طول و عرض پوستر پارسا و همچنین طول و عرض برد دانشگاه همگی زوج است. منظور از نقطه‌ی وسط یک مستطیل نقطه‌ای است که فاصله‌اش از چهار گوشه مستطیل برابر است. در ‌kk سطر بعدی در هر سطر به ترتیب چهار عدد (x1,y1,x2,y2)(x_{1} , y_{1}, x_{2},y_{2}) می‌آید که دو راس روبه‌روی پوستر های روی برد است. مختصات ها به صورت دکارتی بوده و نقطه‌ی گوشه‌ی پایین سمت چپ برد نقطه‌ی (0,0)(0,0) است و نقطه‌ی گوشه بالا سمت راست برد نقطه‌‌ی (w,h)(w,h) است.

1w,h,m,n1 000 000 0001 \le w, h , m , n \le 1\ 000\ 000\ 000 1k100 0001\le k \le 100\ 000 0x1,x2w0 \le x_{1} , x_{2} \le w 0y1,y2h 0\le y_{1} , y_{2} \le h

خروجی🔗

در سطر اول اگر پارسا ‌می‌توانست پوستر را با شرایط گفته شده روی برد بچسباند yes و در غیر این صورت no را چاپ کنید. در صورتی که جواب شما yes بود در سطر بعدی باید مختصات نقطه گوشه چپ پایین پوستر پارسا بر روی برد را چاپ کنید. دقت کنید مکانی که شما برای پوستر پارسا در نظر می‌گیرید باید تمام شرایط گفته شده را داشته باشد یعنی هم باید در دید باشد(به تعریف در دید بودن مراجعه کنید) و هم نباید روی هیچ یک از پوستر‌های روی برد قرار بگیرد. (اگر چند جواب وجود داشت به دلخواه یک جواب را چاپ کنید.)

مثال🔗

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

4 4 2 2 1 
2 0 4 4 
Plain text

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

yes
0 1 
Plain text

توضیح نمونه ۱ : پوستر به رنگ آبی پوستری است که پارسا چسبانده، همچنین نقطه سفید، نقطه‌ی وسط بُرد اصلی دانشگاه و نقطه سیاه نقطه‌ی وسط پوستر پارسا می‌باشد. (دقت کنید که در این نمونه انتخاب پارسا یکتا است و نمی‌تواند جای دیگری را برای پوسترش انتخاب کند.)

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

8 8 2 4 2
7 6 8 2 
0 0 5 4
Plain text

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

yes
3 4
Plain text

توضیح نمونه ۲ : پوستر به رنگ آبی پوستری است که پارسا چسبانده (پارسا در این نمونه ۲ انتخاب دارد که یکی از انتخاب‌ها را در شکل زیر مشاهده می‌کنید)، همچنین نقطه سفید، نقطه‌ی وسط بُرد اصلی دانشگاه و نقطه سیاه نقطه‌ی وسط پوستر پارسا می‌باشد. (دقت کنید که پارسا همیشه پوستر را بدون هیچ دورانی می‌چسباند.)

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.