Kiểm soát không lưu


Submit solution

Points: 1.40 (partial)
Time limit: 1.5s
Memory limit: 256M

Problem type

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 độ, 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 phần tư đường tròn. Góc trái dưới của hình chữ nhật có tọa độ (\(X_{1}\) , 0), góc phải trên là \((X_{2},Y_{2})\). 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_{1} = 2, X_{2} = 11, Y_{2} = 7, R = 1\).

image

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_{1}+ 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.

Input

Dữ liệu

  • Dòng thứ nhất ghi 4 số nguyên \(X_{1}\) , \(X_{2}\) , \(Y_{2}\) , \(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.

Giới hạn

  • \(2 \leq N \leq 10\).
  • \(0 \leq X_{1} < X_2 \leq 100\)
  • \(0 \leq Y_{2} \leq 100\).
  • \(0 < 2R < Y, 0 < 2R < X_2 - X_1\)
  • \(0 < P_{U} \leq 100\).
  • Luôn có một cách sắp xếp các máy bay hạ cánh.

Output

  • 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).
  • Sai số tối đa cho đáp án của bạn so với VNOI là \(10^{-6}\).

Giới hạn

Trong các test chiếm \(60\%\) số điểm, \(2 \leq N \leq 8\).

\(40\%\) số điểm còn lại không có giới hạn gì thêm.

Sample Input

2 11 7 1
2
6 0 40
11 3 25

Sample Output

2.271238898

Note

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.


Comments

There are no comments at the moment.