LEM - RIVER
Giới hạn- Thời gian: 0.059s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Do nhà và trường của Zone nằm ở hai bên bờ của một con sông nên hàng ngày cậu phải đi đò qua sông để đi học. Zone cảm thấy rằng hành trình của ông lái đò là không tối ưu và Zone muốn tìm ra một đường đi tốt hơn.
Sau khi quan sát và đo đạc, Zone có thể biểu diễn được con sông bằng cách chỉ ra 2 bờ của nó. Mỗi bờ sông sẽ được biểu diễn bằng 1 đường gấp khúc và được xác định bằng tọa độ của các điểm trên đường gấp khúc đó như sau:
Đường gấp khúc biểu diễn bờ phía Đông của sông có N điểm, điểm thứ i có tọa độ (x i , y i ).
Đường gấp khúc biểu diễn bờ phía Tây của sông có M điểm, điểm thứ j có tọa độ (u j , v j ).
Biết rằng 2 bờ sông không có điểm chung và y i < y i+1 với mọi 1 ≤ i < N và v j < v j+1 với mọi 1 ≤ j < M.
Bạn hãy tìm 2 điểm A và B sao cho A nằm trên bờ Đông của con sông và B nằm trên bờ Tây của con sông và khoảng cách AB là nhỏ nhất.
Input
- Dòng đầu ghi 2 số nguyên dương N và M.
- Dòng thứ i trong N dòng tiếp theo ghi 2 số nguyên x i , y i .
- Dòng thứ j trong M dòng tiếp theo ghi 2 số nguyên u j , v j .
Output
- Gồm 1 dòng duy nhất ghi khoảng cách ngắn nhất tìm được
( Các số thực được ghi với độ chính xác 3 chữ số sau dấu phẩy )
Example
Input: 3 4 4 0 3 2 5 4 0 0 2 2 1 3 2 5 Output: 1.000
Giới hạn
- 2 ≤ M, N ≤ 1000
- |x i |, |y i |, |u j |, |v j | ≤ 10000
- Người up: cun
- Nguồn bài: Lê Huy Bình