A problem with a sussy content

Điểm: 2500 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 20M

Input: bàn phím

Output: màn hình

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Đây là một câu chuyện có thật, tuy nhiên đã được biển đổi một chút.

Bạn cũng nên thử bài này

TLEoj được nhiều người biết đến là một trang chấm bài trực tuyến với vô vàng bài tập thú vị và những con người thân thiện. Ngoài ra, TLEoj cũng thường xuyên tổ chức các cuộc thi lập trình để những người nơi đây học hỏi thêm nhiều điều mới lạ hơn. Sau những cuộc thi ấy là một nhóm setter chăm chỉ, thường nghĩ ra những bài tập hay ho, thú vị cho mọi người nơi đây làm và flo của chúng ta là một trong số đó.

Sau một giấc ngủ thoải mái, flo tỉnh dậy và kiểm tra tin nhắn của mình. Bỗng cậu thấy có một tin nhắn được gửi đến với nội dung như sau:

Nội dung tin nhắn

Nhóm setter TLEoj bọn bây quá gà, set toàn bài dở mà bày đặt tổ chức contest. Toàn mấy bài rách không ai thèm làm.

Vì là một trong những admin chính của TLEoj, flo đã rất bực mình và cay cú với người gửi tin nhắn trên. Thế là cậu bắt tay vào làm ngay một bài siêu khó để gửi lại cho người ấy như là một thử thách. Bài ấy có nội dung được tiết lộ như sau.

Nội dung bài

Cho $n$ điểm cùng với $1$ điểm $O$ trên mặt phẳng tọa độ, điểm thứ $i$ có tọa độ là $(x_i, y_i)$ , điểm $O$ có tọa độ là $(x_o, y_o)$ và các tọa độ sẽ phân biệt với nhau. Giá trị $D$ của $2$ điểm $(x_i, y_i), (x_j, y_j)$ là khoảng cách ngắn nhất giữa đường thẳng cắt hai điểm đó và điểm $O$ .

Nhiệm vụ của bạn là tìm giá trị $D$ của $2$ điểm bất kỳ trong $n$ điểm trên sao cho nó có giá trị lớn thứ $n$ .

Tuy là người ra bài nhưng flo lại không thể nào giải được bởi lẽ nó quá khó. Là một con người thân thiện ở TLEoj, bạn hãy giúp flo nhé.

Input, Output and Scoring

Input

Ba số nguyên dương $n, x_o, y_o$ $(3 \le n \le 2 \times 10^5; -10^6 \le x_o, y_o \le 10^6)$ .
$n$ dòng tiếp theo, dòng thứ $i$ chứa tọa độ điểm $i$ là $(x_i, y_i)$ $(-10^6 \le x_i, y_i \le 10^6)$ .

Output

In ra giá trị $D$ và lấy $8$ chữ số thập phân đầu tiên.
Kết quả của bạn sẽ được chấp nhận nếu chênh lệch giữa nó và đáp án không quá $10^{-8}$ .

Scoring

Subtask $1$ $(30\%)$ : $1 \le n \le 2 \times 10^3$ .
Subtask $2$ $(70\%)$ : Không giởi hạn gì thêm.

Example

Input

Output

0.42399824

Note

Ta có thể thấy khoảng cách từ $O$ đến đường thẳng $AB$ là lớn thứ $3$ .
Hình ở dưới có $1$ chút sai lệch mà mình chỉnh không được dẫn đến kết quả khác ở trên.

Bình luận

0

flo, 4:30 p.m. 2 Tháng 10, 2023

dead problem