Bạn lái một chiếc thuyền từ tọa độ \((-10,A)\) đến tọa độ \((10,B)\). Tọa độ được đo bằng kilômét và thuyền di chuyển với vận tốc không đổi 1 kilômét mỗi giờ. Bạn hoàn toàn điều khiển được lộ trình của thuyền. Ta mô hình hóa thuyền như một điểm.

Trong khu vực có \(N\) hòn đảo; mỗi đảo cũng được mô hình hóa như một điểm. Đảo thứ \(i\) ở tọa độ \((0,C_i)\).

Khu vực bị nhiễm phóng xạ và bạn liên tục nhận 1 microsievert bức xạ mỗi giờ từ môi trường chung, bất kể đang ở đâu. Hơn nữa, chính các đảo cũng có phóng xạ: bạn liên tục nhận thêm bức xạ từ đảo thứ \(i\) với tốc độ \(D_i^{-2}\) microsievert mỗi giờ, trong đó \(D_i\) là khoảng cách hiện tại tính bằng kilômét từ bạn đến đảo thứ \(i\). Một cách hình thức, gọi \(D_i(t)\) là khoảng cách đến đảo thứ \(i\) theo thời gian \(t\), và \(X\) là tổng thời gian hành trình; tổng bức xạ nhận từ đảo thứ \(i\) là tích phân xác định \(\int_0^X D_i(t)^{-2}\,dt\). Bạn có thể đến gần đảo tùy ý miễn không trùng đúng tọa độ của nó.

Hãy tìm tổng liều bức xạ nhỏ nhất có thể nhận nếu chọn lộ trình tối ưu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa ba giá trị: số nguyên \(N\) và hai số thực \(A,B\) như mô tả trên. Dòng thứ hai chứa \(N\) số thực \(C_i\); số thứ \(i\) là tung độ của đảo thứ \(i\).

Mọi số thực đều được cho với đúng hai chữ số sau dấu thập phân.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là liều bức xạ nhỏ nhất tính bằng microsievert nhận được trong hành trình.

y được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-3}\) so với đáp án chính xác.

Ràng buộc

• \(-10.00\le A\le10.00\).
• \(-10.00\le B\le10.00\).
• \(-10.00\le C_i\le10.00\) với mọi \(i\).
• \(C_i\ne C_j\) với mọi \(i\ne j\).

Phân nhóm

• Test Set 1 (Hiển thị): \(T\le20\), \(N=1\).
• Test Set 2 (Ẩn): \(T\le50\), \(1\le N\le2\).

Đ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ụ

2
1 1.00 -2.00
0.00
2 0.00 0.00
3.00 -3.00

Case #1: 21.806
Case #2: 21.706

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Radioactive Islands.

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