Bắt vật thể trên đường gấp khúc

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một vật thể chuyển động trong không gian ba chiều dọc theo một đường gấp khúc với các đỉnh lần lượt là $(x_{0}, y_{0}, z_{0}), (x_{1}, y_{1}, z_{1}), \dots, (x_{n}, y_{n}, z_{n})$ . Tại thời điểm $t = 0$ , vật thể nằm tại điểm $(x_{0}, y_{0}, z_{0})$ và di chuyển với tốc độ không đổi $v_{s}$ theo các đoạn của đường gấp khúc (đi qua từng đoạn $(x_{i - 1}, y_{i - 1}, z_{i - 1}) \to (x_{i}, y_{i}, z_{i})$ theo thứ tự). Hai đỉnh liên tiếp luôn khác nhau.

Một người chơi xuất phát tại điểm $(P_{x}, P_{y}, P_{z})$ ở thời điểm $t = 0$ và có thể di chuyển theo bất kỳ hướng nào với tốc độ không đổi $v_{p}$ hoặc đứng yên. Đảm bảo $v_{p} \geq v_{s}$ .

Người chơi bắt được vật thể khi cả hai cùng nằm tại một điểm tại cùng một thời điểm. Hãy tìm thời điểm sớm nhất người chơi có thể bắt được vật thể trong khi nó vẫn đang di chuyển trên đường gấp khúc (kể cả tại điểm cuối $(x_{n}, y_{n}, z_{n})$ ), hoặc xác định rằng điều đó không thể xảy ra.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số đoạn của đường gấp khúc.
$n + 1$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_{i}, y_{i}, z_{i}$ — toạ độ đỉnh thứ $i$ (đánh chỉ số từ $0$ ).
Dòng tiếp theo chứa hai số nguyên $v_{p}$ và $v_{s}$ .
Dòng cuối chứa ba số nguyên $P_{x}, P_{y}, P_{z}$ — toạ độ xuất phát của người chơi.

Dữ liệu ra

Nếu người chơi không thể bắt được vật thể, in một dòng duy nhất chứa NO.
Ngược lại, in YES trên dòng thứ nhất, thời điểm bắt được $t$ trên dòng thứ hai, và toạ độ điểm bắt $X Y Z$ trên dòng thứ ba.

Sai số tuyệt đối hoặc tương đối của đáp án không được vượt quá $10^{- 6}$ .

Ràng buộc

$1 \leq n \leq 10 000$ .
$| x_{i} |, | y_{i} |, | z_{i} |, | P_{x} |, | P_{y} |, | P_{z} | \leq 10^{4}$ .
$1 \leq v_{s} \leq v_{p} \leq 10^{4}$ .
Mọi giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

Input	Output	Giải thích
4 0 0 0 0 10 0 10 10 0 10 0 0 0 0 0 1 1 5 5 25	YES 25.5000000000 10.0000000000 4.5000000000 0.0000000000	Vật thể đi hết ba đoạn đầu (tổng độ dài $30$ , hết $30$ giây thì tới $(10, 0, 0)$ ). Tại $t = 25.5$ vật thể đang ở $(10, 4.5, 0)$ trên đoạn thứ ba; người chơi xuất phát từ $(5, 5, 25)$ có khoảng cách tới điểm này đúng $25.5$ , vừa đủ để tới nơi với $v_{p} = 1$ .
4 0 0 0 0 10 0 10 10 0 10 0 0 0 0 0 1 1 5 5 50	NO	Toàn bộ đường gấp khúc dài $40$ nên vật thể chỉ tồn tại trong $40$ giây. Khoảng cách từ người chơi tới mọi điểm trên đường đều lớn hơn $40$ , nên người chơi không kịp bắt.
1 1 2 3 4 5 6 20 10 1 2 3	YES 0.0000000000 1.0000000000 2.0000000000 3.0000000000	Người chơi xuất phát đúng tại điểm $(1, 2, 3)$ — vị trí của vật thể tại $t = 0$ , nên bắt được ngay lập tức.

Bình luận

Không có bình luận tại thời điểm này.