Thử nghiệm bom

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 5.0s
Memory limit: 640M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.