Thử nghiệm bom

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 5.0s
Giới hạn bộ nhớ: 640M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Sau khi xem zootube và được NTN truyền cảm hứng, Thế quyết định rủ Kiên thử nghiệm nổ bom tại nhà.

Khuôn viên vườn nhà Kiên là một mặt phẳng ~O_{XY}~ dài rộng vô hạn. Trong vườn, bố Kiên có ~n~ cây cổ thụ quý đặt ở các vị trí ~P_i(X_i, Y_i)~.

Thế sẽ sắp xếp đặt một quả bom tại điểm ~O(0, 0)~, trong khi đó Kiên sẽ đặt ~m~ tấm màn chắn để bảo vệ những cây cổ thụ khỏi tác động của quả bom. Các tấm màn chắn Kiên chọn có thể tưởng tượng như một đường thẳng dài vô hạn trên mặt phẳng tọa độ (các tấm màn chắn có thể giao nhau).

Vì mục đích thử nghiệm khoa học, quả bom lần này Thế và Kiên chọn sẽ mang cả các chất phóng xạ, do đó, một cây cổ thụ chỉ có thể được bảo vệ nếu đường thẳng nối giữa vị trí của nó và tâm ~O(0, 0)~ giao với ít nhất một tấm màn chắn.

Các tấm màn chắn cũng sẽ hạn chế phản ứng phát nổ của quả bom, do đó Kiên muốn đặt các tấm màn chắn xa quả bom nhất có thể. Nói cách khác, Kiên muốn khoảng cách giữa tâm quả bom và tấm màn chắn gần tâm nhất là lớn nhất.

Gọi khoảng cách trên là ~R~. Nhiệm vụ của bạn là giúp Kiên tìm ~R~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n, m (1 \leq n, m \leq 10^{5})~.

Dòng thứ ~i~ trong ~N~ dòng tiếp theo là hai số nguyên ~X_i, Y_i(-10^{5} \leq X_i, Y_i \leq 10^{5})~, tương ứng với tọa độ ~P_i~ của cây cổ thụ thứ ~i~.

Output

In ra một số thực duy nhất là kết quả ~R~ của bài toán. Đáp án của bạn sẽ được chấp nhận nếu sai số so với đáp án của giám khảo nhỏ hơn ~10^{-3}~.

Example 1

3 1
4 0
0 3
-2 0
0.000000000

Example 2

3 1
0 0
0 0
0 0
0.000000000

Example 3

4 2
2 2
2 3
3 2
3 3
2.828427125

Bình luận

Hãy đọc nội quy trước khi bình luận.


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