Марсохід

Космічний апарат "North-2006" успішно досяг Марса, а спуск ровера пройшов за планом. Хоча ровер сконструйований для руху по складній місцевості, зайвих ризиків слід уникати. Ідеально, якщо ровер дістанеться від початкової точки до кінцевої, не перетинаючи жодного кратера. "North-2006" зробив знімок місцевості з космосу. Ваше завдання — написати програму, яка, маючи зображення разом із початковими та кінцевими координатами ровера, визначає, чи існує безпечний шлях для ровера від початку до пункту призначення.

Формалізуємо задачу.

Фотографія місцевості — це квадрат, у якого лівий нижній кут має координати $(0,0)$, а правий верхній — $(1000,1000)$. Ровер вважається кругом радіуса $r$. На фотографії видно $n$ помітних кратерів, кожен з яких має форму кола. Центр $k$-го кратера має координати (x_k, y_k), а його радіус — r_k. Спочатку ровер розташовується у лівому нижньому куті карти, тобто його центр знаходиться у точці (r, r). Мета ровера — дістатися до правого верхнього кута карти, тобто до точки (1000 - r, 1000 - r). Щоб шлях вважався безпечним, ровер не повинен залишати межі карти (хоча може торкатися до країв), а також не повинен проїжджати по кратерах (хоча може їх торкатися). Кратери можуть перекриватися, і якщо один кратер повністю знаходиться всередині іншого, внутрішній можна ігнорувати.