المپدیا

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

ابزار کاربر

ابزار سایت


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

محقق احمق

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

ورودی

ابتدا $n$ تعداد کوه‌ها و سپس $n$ جفت عدد که مختصه‌ی $x$ مرکز و شعاع کوه آمده است. بالطبع $y$ مرکز همه‌ی کوه‌ها صفر است. ($0\leq m \leq 10^5$ و $0 \leq n \leq 10^5$ و $0\leq x \leq 10^9$. شعاع کو‌ها مثبت و کم‌تر از $10^5$ می‌باشد.)

سپس $m$ تعداد شهاب‌سنگ‌ها و بعد $m$ عدد که مختصه‌ی $x$ سقوط شهاب‌سنگ داده می‌شود. شهاب‌سنگ‌ها عمودی سقوط می‌کنند.

خروجی

$m$ جفت عدد حقیقی که مختصات $x$ و $y$ محل ایستادن شهاب‌سنگ‌ها به همان ترتیب ورودی می‌باشد.

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

ورودي نمونه خروجي نمونه
3
10 5
30 5
36 5
4
50 10 11 32
50 0
10 5
15 0
33 4

ابزار صفحه