Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LEM - RIVER

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274821/problem/B

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 độ (xi, yi).

Đườ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 độ (uj, vj).

Biết rằng 2 bờ sông không có điểm chung và yi < yi+1 với mọi 1 ≤ i < N và vj < vj+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 xi, yi.

- Dòng thứ j trong M dòng tiếp theo ghi 2 số nguyên uj, vj.

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
  • |xi|, |yi|, |uj|, |vj| ≤ 10000

Được gửi lên bởi:special_one
Ngày:2008-03-26
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Lê Huy Bình

hide comments
2019-09-12 05:36:06
TFT rank > bkim 3 cho sub :))
2017-08-10 07:16:04
đề rất troll
2017-07-03 17:52:10
bài này đề chỗ nào thế -_-
2016-08-01 17:17:12
Nhan danh tinh tế,... dùng thuật toán giải HPT thì nên đặt dạng phương trình : Ax + By = C cho lành nhá :3
2014-11-12 01:28:39 NTIT_Trường Kỳ
cẩn thận đọc không kỹ đề sẽ được 63,64 ^_^
2014-05-29 06:40:28 Nắng
càng sửa càng giảm điểm @@ ko hiểu sao :|
2014-05-29 05:48:12 Kraken
giới hạn 1000 mà không O(n^2) được à!
2014-05-27 07:06:59 Anh Duc Le
bao nhiêu lần sub chỉ vì nhầm i với j :((
2014-05-27 03:54:13 Lollipop


Last edit: 2014-05-27 04:29:48
2014-05-26 17:37:26 Lollipop


Last edit: 2014-05-26 18:01:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.