ROADCBG - Vượt qua đường
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: mikelhpdatke

          Trong một buổi diễn tập quân sự đơn vị trinh sát có nhiệm vụ vượt qua phòng tuyến bảo vệ, thâm nhập vào hậu cứ của đối phương. Phòng tuyến bảo vệ là một đường thẳng trống trải, các vị trí trên đó được đánh số như một trục tọa độ. Có n đèn pha liên tục quét chiếu sáng các đoạn đường. Tại thời điểm 0, đèn thứ i bắt đầu bật chiếu sáng trong khoảng [ai, bi] (mét) và di chuyển theo đường bảo vệ với tốc độ vi (mét/giây).  Nếu ai <bi đoạn chiếu sáng di chuyển theo chiều tăng dần của trục tọa độ, còn nếu ai > bi - di chuyển theo chiều ngược lại (một đèn pha chỉ đi theo một hướng, không quay ngược lại). Các đoạn được chiếu sáng có thể rời nhau hoặc đè lên nhau.

         Đơn vị trinh sát có m người, sẽ vượt qua đường ở điểm có tọa độ x. Người thứ j tới điểm cần vượt ở thời điểm tj (giây) và chỉ vượt qua đường khi điểm x không bị đèn nào chiếu sáng, không được vượt kể cả ở 2 đầu x = ai hoặc x =  bi.

Thời gian vượt qua đường coi như không đáng kể.

Với mỗi người hãy xác định thời điểm sớm nhất có thể vượt qua đường và đưa ra độ chính xác 10-6.

Dữ liệu:

- Dòng thứ nhất 3 số nguyên n, m, x (1 ≤ n, m ≤ 105, -109 ≤ x ≤ 109).

- Dòng thứ i trong n dòng tiếp theo chứa 3 số nguyên a, b, v (-109 ≤ a, b ≤ 109, v ≤ 109, a ≠ b).

- Chứa m số t (0 ≤ t ≤ 109).

Kết quả:

- Gồm m dòng, mỗi dòng một số là kết quả tìm được. Kết quả được làm tròn đến 6 số sau dấu thập phân và phải in đủ 6 số sau dấu thập phân.

C++: dùng cout<<fixed<<setprecision(6);

Ví dụ

  • input
    3 2 0
    -4 -1 1
    13 6 3
    -7 -6 1
    1 5
    output
    4.333333
    5.000000

Tại thời điểm 4.333333... đèn số 2 quét xong tọa độ 0. Người thứ nhất có thể vượt đường sau đó một chút. Nhưng do làm tròn nên kết quả cũng là 4.333333

Back to Top