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

Đề bài

Mô tả

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à (x0,y0,z0),(x1,y1,z1),,(xn,yn,zn). Tại thời điểm t=0, vật thể nằm tại điểm (x0,y0,z0) và di chuyển với tốc độ không đổi vs theo các đoạn của đường gấp khúc (đi qua từng đoạn (xi1,yi1,zi1)(xi,yi,zi) 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 (Px,Py,Pz) ở 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 vp hoặc đứng yên. Đảm bảo vpvs.

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 (xn,yn,zn)), 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 xi,yi,zi — toạ độ đỉnh thứ i (đánh chỉ số từ 0).
  • Dòng tiếp theo chứa hai số nguyên vpvs.
  • Dòng cuối chứa ba số nguyên Px,Py,Pz — 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 XYZ 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á 106.

Ràng buộc

  • 1n10000.
  • |xi|,|yi|,|zi|,|Px|,|Py|,|Pz|104.
  • 1vsvp104.
  • 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 vp=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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0