Thi lập trình trực tuyến

Với sự phát triển ngày càng nhanh của hàng không Việt Nam, sân bay Nội Bài đã trở nên quá nhỏ bé. Sân bay chỉ có một đường băng và các máy bay khi bay tới Hà Nội sẽ phải bay lòng vòng phía trên để chờ được hạ cánh.

Để đơn giản, ta hãy mô tả sân bay trên mặt phẳng tọa độ Đề Các, mỗi đơn vị độ dài sẽ tương đương 1 Km. Đường băng của sân bay là một đoạn thẳng từ (0, 0) đến (-7, 0). Các máy bay khi đến Hà Nội sẽ phải bay ở khu vực chờ, đó là một hình có dạng hình chữ nhật với bốn góc là các đoạn ¼ đường tròn. Góc trái dưới của hình chữ nhật có tọa độ (X₁, 0), góc phải trên là (X₂, Y₂). Các góc phần tư hình tròn có bán kính là R. Dưới đây là ví dụ với X₁ = 2, X₂ = 11, Y₂ = 7, R = 1.

Các máy bay sẽ bay với cùng vận tốc 10 Km/phút và theo hướng cùng chiều kim đồng hồ. Khi được phép hạ cánh, máy bay phải bay tới vị trí (X₁ + R, 0) (vị trí được đánh dấu hình tròn màu đỏ trên hình vẽ) rồi từ đó bay thẳng vào đường băng. Tại thời điểm ban đầu, có N máy bay, tại các tọa độ (X_U, Y_U). Với mỗi máy bay, ta được biết lượng nhiên liệu còn lại đủ để đi quãng đường là P_U (Km). Máy bay được coi là hạ cánh an toàn nếu nó đủ nhiêu liệu để bay đến điểm có tọa độ (0, 0) (đầu đường băng).

Bạn hãy sắp xếp thứ tự được hạ cánh của các máy bay sao cho thời gian hạ cánh gần nhất giữa 2 máy bay liên tiếp là lớn nhất có thể được, điều này sẽ tăng độ an toàn của các lần hạ cánh.

Dữ liệu

• Dòng thứ nhất ghi 4 số nguyên X₁, X₂, Y₂, R.
• Dòng thứ hai ghi số N.
• Tiếp theo là N dòng, mỗi dòng ghi 3 số thực X_U, Y_U, P_U.
• Dữ liệu đảm bảo máy bay đang bay trên các cạnh thẳng của khu vực chờ. Lưu ý rằng các máy bay có thể ở cùng vị trí vì khi độ cao chênh lệch khác nhau thì vẫn đảm bảo độ an toàn.

Kết quả

• Ghi ra duy nhất thời gian hạ cánh gần nhất giữa 2 máy bay liên tiếp (tính theo phút) với độ chính xác là 1e-6.

Ví dụ

Dữ liệu
2 11 7 1
2
6 0 40
11 3 25	

Kết quả
2.271238898

Giải thích

Máy bay #2 chỉ còn bay được 25 Km và phải được ưu tiên hạ cánh ngay. Máy bay #2 sẽ hạ cánh sau khi bay thêm khoảng 13.57079633 Km nữa. Máy bay #1 cũng có thể hạ cánh ngay nhưng sẽ an toàn hơn nếu máy bay #1 bay thêm 1 vòng nữa. Tổng cộng máy bay #1 sẽ bay thêm 36.28318531 Km.

Giới hạn

• 2 ≤ N ≤ 10, trong các test chiếm 60% số điểm, 2 ≤ N ≤ 8
• 0 ≤ X₁ ≤ 100
• X₁ < X₂ ≤ 100
• 0 < Y₂ ≤ 100
• 0 < 2R < Y, 0 < 2R < X₂ – X₁
• 0 < P_U ≤ 100
• Luôn có một cách sắp xếp các máy bay hạ cánh.