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.|

KTOUR - Đi chơi

Điều tối kỵ khi có nhiều bạn gái là gì? Là để họ gặp nhau...

Tuy nhiên, vào một ngày nọ tai họa bỗng nhiên ập xuống đầu Pirate khi tất cả N cô bạn gái của anh ta cùng một lúc muốn đi chơi với anh chàng. Dĩ nhiên là anh ấy không bao giờ bó tay chịu bị "ngũ mã phanh thây", nên đã sắp xếp hẹn mỗi em trên một hòn đảo khác nhau. Các hòn đảo này có vị trí rất đặc biệt. Nếu nhìn vào bản đồ biển (là hệ trục tọa độ xy), thì các hòn đảo này là các điểm nằm trên một đường thẳng song song với trục hoành.  

Giờ điều duy nhất là Pirate băn khoăn là dắt các em đi đâu đây nhỉ? Có M chốn hẹn hò lãng mạn trên vùng biển này, mỗi nơi được biểu diễn bởi một điểm trên bản đồ. Pirate muốn "giữ sức" và "giữ tiền" để có đi chơi hết với mọi em. Thế anh quyết định là sẽ dẫn mỗi em đến nơi hẹn hò gần nhất với hòn đảo họ đang đứng. Sau khi xếp lịch xong, Pirate tự hỏi mình phải đi quãng đường xa nhất là bao nhiêu để chuẩn bị tiền đổ xăng (đã qua rồi cái thời cướp biển và cánh buồn phiêu du)?

Input

  • Dòng thứ nhất: hai số nguyên N - số hòn đảo hẹn hò, và Y0 - tọa độ y của các hòn đảo.
  • N dòng tiếp theo: mô tả tọa độ x của các hòn đảo.
  • Dòng thứ N + 2: số nguyên M - số địa điểm hẹn hò lãng mạn.
  • M dòng tiếp theo: mô tả tọa độ (x, y) của các nơi hẹn hò.

Output

  • Một dòng duy nhất ghi ra khoảng cách lớn nhất mà Pirate phải đi từ một hòn đảo đến nơi hẹn hò tương ứng (làm tròn đến 6 chữ số thập phân sau dấu chấm).

Giới hạn

  • Mọi số trong input đều là số nguyên không âm và không vượt quá 105
  • 60% số test có 1 ≤ N, M ≤ 1000.

Example

Input:
2 1 
1
2
2
0 2
1 0

Output:
1.414214

 

Giải thích: Có 2 hòn đảo nằm ở (1, 1) và (2, 1) và 2 địa điểm hẹn hò ở (0, 2) và (1, 0). Vì Pirate chỉ chọn nơi hẹn hò gần nhất với hòn đảo đang đứng, nên từ hai hòn đảo, anh ấy đều đi đến nơi hẹn hò đầu tiên với khoảng cách lần lượt là 1 và 1.414214. Đáp án của bài toán là khoảng cách lớn nhất 1.414214.
 


Được gửi lên bởi:Nguyễn Xuân Khánh
Ngày:2011-06-26
Thời gian chạy:1.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC GAWK MAWK BC C-CLANG C++ 4.3.2 CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PAS-FPC PICO PROLOG PY_NBC R RACKET CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

hide comments
2018-10-10 10:31:05
Hoàng cứt đã đưa tôi tới đây!
2016-05-03 16:28:33 Nguyen Cuong
sao mà đào hoa thế này -_- đọc đề thôi cũng thấy ghen tị :v
2015-07-04 09:42:18 CK
dpt O(n+2*10^5) time 0.27s =))
2014-01-27 06:14:50 Discite4ever
Mọi người để ý là bộ test có vấn đề nhaz. Các hòn đảo có thể trùng nhau :|.
2013-01-01 15:29:11 Shinken Yellow
cánh buồn =))
2011-11-04 09:28:39 Nguyễn Hữu Hùng
60% số test có 1 ≤ N, M ≤ 1000 sao duyệt trâu cũng chỉ được 26.67 điểm vậy PS?

Chặt nhị phân cũng chỉ được 26.67. PS xem hộ bị TLE hay WA.
2011-07-02 18:09:54 Cao Viên Viên
P/s thiếu thốn tình cảm lắm hay sao, Toàn thấy lấy gái ra minh họa thế nhỉ :|
2011-06-28 07:38:56 1212
Cho em hỏi rằng giá giới hạn của n và m là bao nhiêu vậy?
2011-06-27 14:30:43 vn_army
24s , test kinh khung that...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.