Bạn là một chiến binh nổi dậy chống lại Đế chế Thiên hà độc ác, và đang chạy trốn!

Bạn vừa phá hoại Nhà máy Tội ác của Đế chế, và lực lượng an ninh sắp truy đuổi. Nhà máy nằm trên tiểu hành tinh 0 trong một hệ gồm \(N\) tiểu hành tinh được đánh số. Tàu trốn thoát Century Quail nằm trên tiểu hành tinh 1; nếu tới được đó, bạn sẽ bay đi an toàn.

Mỗi tiểu hành tinh là một điểm trong không gian và có vận tốc; bạn chuyển động cùng tiểu hành tinh đang đứng. Thiết bị Asteroid Jumper cho phép nhảy tức thời giữa hai tiểu hành tinh bất kỳ. Cú nhảy dài đáng sợ hơn cú nhảy ngắn, nên bạn muốn tối thiểu hóa khoảng cách lớn nhất phải nhảy. Tuy nhiên, tính từ lúc này, nếu có bất kỳ khoảng thời gian liên tục nào dài quá \(S\) giây mà bạn không nhảy, lực lượng an ninh sẽ bắt được bạn. Khoảng từ lúc bắt đầu đến cú nhảy đầu và mọi khoảng giữa hai cú nhảy liên tiếp đều không quá \(S\). Có thể nhảy ở bất kỳ thời điểm thực nào, không cần chờ số giây nguyên. Bạn thoát ngay khi nhảy tới tiểu hành tinh 1.

Tiểu hành tinh \(i\) bắt đầu tại \((x_i,y_i,z_i)\) và mỗi giây dịch chuyển thêm vectơ \((V_{xi},V_{yi},V_{zi})\). Chuyển động diễn ra liên tục, không cập nhật rời rạc từng giây; một tiểu hành tinh cũng có thể đứng yên. Hai tiểu hành tinh trùng vị trí không gây ra điều gì: bạn vẫn chỉ có thể đi giữa chúng bằng một cú nhảy, kể cả khi khoảng cách đúng bằng 0 ở thời điểm ấy.

Trong kế hoạch trốn thoát tối ưu, khoảng cách của cú nhảy dài nhất là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N,S\): số tiểu hành tinh và thời gian tối đa được phép không nhảy. Tiếp theo là \(N\) dòng, đánh số từ 0; dòng thứ \(i\) chứa sáu số nguyên: vị trí ban đầu \((x_i,y_i,z_i)\) và vectơ dịch chuyển trong một giây \((V_{xi},V_{yi},V_{zi})\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ 1, còn y là khoảng cách cú nhảy dài nhất cần thực hiện. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-4}\).

Ràng buộc

• \(1\le T\le20\).
• \(2\le N\le1000\).
• \(1\le S\le100\).
• \(-500\le x_i,y_i,z_i\le500\).

Phân nhóm

Test Set 1 (Small, hiển thị)

\(V_{xi}=V_{yi}=V_{zi}=0\).

Test Set 2 (Large, ẩn)

\(-500\le V_{xi},V_{yi},V_{zi}\le500\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3 7
0 0 0 0 0 0
1 2 2 0 0 0
1 1 1 0 0 0
5 10
0 0 0 0 0 0
35 0 0 -1 0 0
1 54 0 0 -2 0
2 -150 0 0 10 0
4 0 0 -1 0 0
3 1
-10 2 0 1 0 0
0 0 10 0 0 -1
-10 -2 0 1 0 0

Case #1: 1.7320508
Case #2: 2.0000000
Case #3: 4.0000000

Nguồn

Google Code Jam 2016, Vòng 3, bài Rebel Against The Empire.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.