trang chủ / đề bài / icpcwf14_f

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à 1 đơ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 n là số địa điểm được ghé thăm. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên xi và yi 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á 10−3 hoặc sai số tương đối không vượt quá 10−5. Nếu không thể giao gói hàng, in ra impossible.

Ràng buộc

  • 2≤n≤50000 (với mỗi đường đi).
  • 0≤xi,yi≤30000.
  • 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á 106.

Ví dụ

Input Output Giải thích
2
0 0
0 10
2
4 10
4 0
4.00000 Misha đi từ (0,0) lên (0,10), Nadia đi từ (4,10) xuống (4,0). Misha trao gói hàng lúc t=3 tại (0,3), người đưa thư chạy ngang tới (4,3) và gặp Nadia lúc t=7. Thời gian giao hàng là 4.
2
0 0
1 0
3
2 0
3 0
3 10
5.00000 Misha trao gói hàng ngay lúc t=0 tại (0,0). Người đưa thư chạy thẳng tới (3,4), quãng đường 5, và gặp Nadia tại đó lúc t=5.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0