1040 - OLP 2019 - Cột bò

Tạo bởi: CLB Olympic Tin học HUTECH

Mô tả yêu cầu

Trên khu đất rộng nhà Hoàng có n đống rơm, đó là thức ăn dự trữ cho chú bò vào mùa đông. Mỗi đống rơm được biểu diễn là một hình tròn trên mặt phẳng tọa độ, đống rơm thứ i có tọa độ tâm là (x_i, y_i) và bán kính r_i. Tại điểm (a, b) có một cọc để cột chú bò.

1603119672-78aa8aa84f-CotBo.png

Vào mỗi buổi chiều tối hàng ngày, Hoàng cột chú bò của mình vào cọc bằng một sợi dây. Nếu sợi dây có độ dài l thì chú bò có thể di chuyển trong vòng tròn tâm (a, b) và bán kính l.

Yêu cầu: Hãy tìm độ dài l nguyên lớn nhất sao cho chú bò không thể ăn rơm từ bất kì một đống rơm nào. Chú ý rằng, chú bò có thể ăn rơm của đống thứ i nếu đường tròn tâm (a, b) bán kính l và đường tròn tâm (x_i, y_i) bán kính r_i có điểm chung.

Dữ liệu vào

Vào từ file văn bản có định dạng như sau:

  • Dòng đầu số chứa ba số nguyên n, a, b (\vert a \vert, \vert b \vert \leq 10^9)
  • Dòng thứ i trong n dòng tiếp theo chứa ba số nguyên x_i, y_ir_i (\vert x_i \vert, \vert y_i \vert, r_i ≤ 10^9).

Chú ý:

  • Có 50% số test có n = 1
  • Có 50% số test có n < 100

Dữ liệu ra

Ghi ra một dòng chứa một số nguyên l lớn nhất thỏa mãn.

Ví dụ

Dữ liệu vào Sao chép
1 0 0
0 9 3
Dữ liệu ra Sao chép
5
Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB