Unenslaved puppy#188

Unenslaved puppy (Editorial)

Купол — це півколо з центром на осі абсцис, крізь стінку якого пройти неможливо. Тому купол відділяє свою внутрішність від решти площини: якщо песик усередині, а вулик зовні (або навпаки), то бджоли до песика не дістануться.

Звідси критерій. Песик у безпеці тоді й лише тоді, коли існує купол, який містить рівно одну з двох точок. Якщо ж для кожного купола обидві точки або всередині, або обидві зовні, жодної перешкоди між ними немає, і бджоли долетять.

Точка $(x, y)$ лежить у куполі $i$ тоді й лише тоді, коли

(x - p o s_{i})^{2} + y^{2} \leq r_{i}^{2}

(x - pos_i)^2 + y^2 \le r_i^2

(за умовою точка на самій стінці вважається всередині, тому нерівність нестрога; усі точки мають $y \geq 0$ y \ge 0, тож нижню половину кола розглядати не треба).

Отже, розв'язок — один прохід по куполах: для кожного перевіряємо, чи всередині песик і чи всередині вулик. Щойно знайшли купол, де ці відповіді різні, виводимо NO і номер цього купола. Якщо жодного такого купола немає — YES.

Важлива технічна порада: не рахуйте відстань через квадратний корінь у дійсних числах — порівнюйте квадрати відстаней у цілих числах. Координати й радіуси не перевищують $1 0^{3}$ 10^3, тому квадрати вміщуються навіть у 32-бітний тип, а порівняння стає точним.

Складність — $O (n)$ .

(x - p o s_{i})^{2} + y^{2} \leq r_{i}^{2}

y \geq 0

1 0^{3}