Người đưa thư
Đề bài
Mô tả
Misha cần gửi các gói hàng cho bạn mình là Nadia. Cả hai thường xuyên đi khắp nước Nga, một đất nước rất rộng lớn. Vì vậy họ quyết định thuê một người đưa thư. Do chi phí dịch vụ đưa thư phụ thuộc vào thời gian giao gói hàng, họ cần bạn giúp tối ưu một chút.
Giả sử Misha và Nadia di chuyển trên một mặt phẳng hai chiều, mỗi người lần lượt ghé thăm một dãy địa điểm và đi theo các đoạn thẳng từ địa điểm này tới địa điểm tiếp theo. Nhiệm vụ của bạn là tìm thời gian giao hàng ngắn nhất có thể khi biết đường đi của cả hai người.
Misha trao gói hàng cho người đưa thư tại một điểm nào đó trên đường đi của mình. Người đưa thư lập tức di chuyển theo một đường thẳng từ điểm nhận hàng để gặp Nadia, người đang di chuyển trên đường đi của cô. Misha, Nadia và người đưa thư đều di chuyển với tốc độ không đổi là đơn vị độ dài trên một đơn vị thời gian. Thời gian giao hàng là khoảng thời gian từ lúc Misha trao gói hàng tới lúc Nadia nhận được nó.
Dữ liệu vào
Dữ liệu vào gồm một bộ test duy nhất, chứa hai mô tả đường đi: đường đi thứ nhất của Misha và đường đi thứ hai của Nadia. Mỗi mô tả đường đi bắt đầu bằng một dòng chứa số nguyên là số địa điểm được ghé thăm. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và là tọa độ của một địa điểm. Các địa điểm được liệt kê theo thứ tự ghé thăm, và hai địa điểm liên tiếp không trùng tọa độ.
Misha và Nadia bắt đầu hành trình cùng một lúc, ghé thăm các địa điểm trên đường đi của mình mà không dừng lại. Gói hàng phải được nhận muộn nhất là lúc Misha tới địa điểm cuối cùng của anh, và phải được giao muộn nhất là lúc Nadia tới địa điểm cuối cùng của cô.
Dữ liệu ra
In ra thời gian nhỏ nhất cần để giao hàng. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá hoặc sai số tương đối không vượt quá . Nếu không thể giao gói hàng, in ra impossible.
Ràng buộc
- (với mỗi đường đi).
- .
- Hai địa điểm liên tiếp trên cùng một đường đi có tọa độ khác nhau.
- Độ dài mỗi đường đi không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 0 0 10 2 4 10 4 0 |
4.00000 | Misha đi từ lên , Nadia đi từ xuống . Misha trao gói hàng lúc tại , người đưa thư chạy ngang tới và gặp Nadia lúc . Thời gian giao hàng là . |
| 2 0 0 1 0 3 2 0 3 0 3 10 |
5.00000 | Misha trao gói hàng ngay lúc tại . Người đưa thư chạy thẳng tới , quãng đường , và gặp Nadia tại đó lúc . |
Bình luận