Đi chơi

View as PDF

Submit solution

Points: 0.99 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đ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 Đạt sát gái khi dàn harem gồm ~N~ cô bạn gái của Đạt 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 xinh tươi trên ~1~ hòn đảo khác nhau.

Hãy tưởng tượng toàn bộ vùng biển một là mặt phẳng toạ độ.

Vì gu mặn nên ~N~ hòn đảo mà Đạt chọn cho ~N~ cô bạn gái đều có vị trí rất đặc biệt. Chúng là các điểm nằm trên một đường thẳng song song với trục hoành. Cũng có nghĩa là, tất cả các hòn đảo đều có cùng tung độ ~Y_0~.

Giờ điều duy nhất là Đạt băn khoăn là dắt các em đi đâu đây nhỉ? Có ~M~ địa điểm 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 có toạ độ ~(x,y)~ trên bản đồ. Đạt muốn "giữ sức" và "giữ tiền" để đi chơi hết với mọi em và hưởng lạc.

Thế nên Đạt 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, Đạt 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 cho con SH?

Input

  • Dòng thứ nhất: hai số nguyên ~N~ - số hòn đảo hẹn hò, và ~Y_0~ - tung độ của các hòn đảo.
  • ~N~ dòng tiếp theo là các hoành độ ~X_1,X_2,\ldots,X_N~ của các hòn đảo.
  • Dòng thứ ~N + 2~ là số nguyên ~M~ - số địa điểm hẹn hò lãng mạn.
  • ~M~ dòng tiếp theo là ~M~ cặp số nguyên ~(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)~ là toạ độ của các địa điểm hẹn hò.

Toạ độ của tất cả các hòn đảo và các địa điểm hẹn hò đều là các số tự nhiên không quá ~10^5~ (vì gu mặn của Đạt).

Output

In ra số thực duy nhất là đáp án của bài toán trên.

Sai số tối đa cho đáp án của bạn so với đáp án của VNOI là ~10^{-6}~.

Giới hạn

  • Có ~60\%~ số test tương ứng với ~60\%~ số điểm của bài có ~1 \leq N,M \leq 10^3~.
  • ~40\%~ số test còn lại không có giới hạn gì thêm.

Sample Input

2 1 
1 
2
2
0 2
1 0

Sample Output

1.414214

Note

Ở test ví dụ, 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ì Đạt mặn 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~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.