H. O'rgimchak odam Erangelda

PUBG Mobile’ning yangi mavsumida O‘rgimchak-odam bilan hamkorlik e’lon qilindi: endi o‘yinchi o‘z ip otuvchisi (web-shooter) yordamida binolar orasida tezda sakrashi mumkin. 

Erangel orolida \(n\) ta bino joylashgan bo‘lib, ularning koordinatalari tekislikda berilgan. O‘yinchi hozir \(1-\)binoda turibdi va faqat binolar orasida (erkin yugurmasdan, faqat bino-bino) harakat qila oladi.

Namunadagi test uchun 1-binodan 2-binoga ip yordamida o‘tish jarayoni.

Ikkita bino orasidagi Yevklid masofasi \(d\) bo‘lsin:

• Agar \(d \le R\) bo‘lsa (\(R\) — ipning maksimal uzunligi), o‘yinchi ip otib sakrashi mumkin — bu safar tezligi \(v_w\) ga teng (\(\text{vaqt} = d / v_w\)).
• Istalgan ikkita bino orasida (masofadan qat'iy nazar) piyoda ham yurish mumkin — tezligi \(v_p\) (\(v_p < v_w\)), ketadigan vaqt esa \(\text{vaqt} = d / v_p\) bo‘ladi.

O‘yinchi har safar ikki variantdan birini tanlaydi (agar \(d \le R\) bo‘lsa, tezroq bo‘lgani uchun odatda ip afzal, lekin bu qat'iy shart emas — masala shuni hisoblab topishi kerak).

O‘yin davomida xavfsiz zona asta-sekin torayib, \(T\) soniyadan so‘ng markazi \((cx, cy)\) da, radiusi \(r\) bo‘lgan yakuniy doiraga aylanadi va shu yerda to‘xtaydi. Omon qolish uchun o‘yinchi \(T\) soniyagacha markazgacha masofasi \(r\) dan oshmaydigan (ya'ni yakuniy doira ichidagi) biror binoga yetib borishi kerak.

O‘yinchi eng qisqa vaqtda yakuniy zonaga yetib bora oladimi? Agar ha bo‘lsa, buning uchun zarur bo‘lgan minimal vaqtni toping.

Kiruvchi ma'lumotlar

Birinchi qatorda \(n\) (\(2 \le n \le 2000\)) — binolar soni beriladi.

Ikkinchi qatorda \(v_p, v_w, R\) — piyoda harakatlanish tezligi, ip yordamida sakrash tezligi va ipning maksimal radiusi (\(1 \le v_p < v_w \le 10^3\); \(1 \le R \le 3 \times 10^5\)) beriladi.

Uchinchi qatorda \(cx, cy, r, T\) — yakuniy xavfsiz zonaning markazi koordinatalari, radiusi va qolgan vaqt (\(-10^5 \le cx, cy \le 10^5\); \(0 \le r \le 3 \times 10^5\); \(1 \le T \le 10^9\)) beriladi.

Keyingi \(n\) ta qatorning har birida \(x_i, y_i\) — \(i-\)binoning koordinatalari (\(-100000 \le x_i, y_i \le 100000\)) beriladi. \(1-\)bino — o‘yinchining boshlang‘ich turgan joyi.

Chiquvchi ma'lumotlar

Agar o‘yinchi \(T\) soniya ichida yakuniy zonaga yetib bora olsa, minimal vaqtni \(10^{-6}\) aniqlikda chop eting. Aks holda — "NO" so‘zini chiqaring.

Misollar

1

2
1 5 10
3 4 1 100
0 0
3 4

1.000000

Izoh

Kirish ma'lumotlari: 
\(n = 2\), \(v_p = 1\), \(v_w = 5\), \(R = 10\), zona markazi \((3, 4)\), \(r = 1\), \(T = 100\); \(1-\)bino \((0, 0)\), \(2-\)bino \((3, 4)\).

1. Masofa: \(d = \sqrt{3^2 + 4^2} = 5\) 
2. \(d = 5 \le R = 10 \) \(\rightarrow\) ip bilan sakrash mumkin: \(t = d / v_w = 5 / 5 = 1.0\) (piyoda bo'lsa \(5.0\) bo'lardi, ip tezroq)
3. Faqat \(2\) bino bo'lgani uchun bu — bevosita eng qisqa yo'l
4. \(2-\)bino markazdan \(0\) masofada, ya'ni \(0 \le r = 1\) \(\rightarrow\) zona ichida
5. \(1.0 \le T = 100\) \(\rightarrow\) javob: YES, \(1.000000\)