Một vườn hoa có rất nhiều bông hoa và hai đài phun nước. Bạn có thể lắp bơm áp lực cho hai đài phun nước để tưới cây và có thể điều chỉnh bán kính tưới của hai đài phun nước là \(r_1, r_2\) (với \(r_1, r_2 \geq 0\)). Mỗi đài phun nước có thể tưới nước cho những bông hoa cách nó không lớn hơn bán kính tưới.
Bạn muốn mọi bông hoa trong vườn đều được tưới nước, đồng thời giá trị \(r_1^2 + r_2^2\) là nhỏ nhất. Bạn hãy tìm giá trị nhỏ nhất này.
Dữ liệu vào
- Dòng đầu tiên chứa 5 số nguyên \(n, x_1, y_1, x_2, y_2\) (\(1 \leq n \leq 10^5\), \(-10^7 \leq x_1, y_1, x_2, y_2 \leq 10^7\)) lần lượt là số bông hoa và tọa độ của hai đài phun nước.
- \(n\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(x_i, y_i\) (\(-10^7 \leq x_i, y_i \leq 10^7\)) là tọa độ của bông hoa thứ \(i\). Tọa độ các bông hoa và đài phun nước là phân biệt.
Dữ liệu ra
- Ghi ra một dòng chứa giá trị \(r_1^2 + r_2^2\) nhỏ nhất. Chú ý rằng trong bài toán này câu trả lời luôn là một số nguyên.
Input 1
2 -1 0 5 3
0 2
5 2
Output 1
6
Input 2
4 0 0 5 0
9 4
8 3
-1 0
1 4
Output 2
33
Ràng buộc:
- 25% test: \(1 \leq n \leq 10^2\), \(-10^3 \leq x_1, y_1, x_2, y_2 \leq 10^3\), \(-10^3 \leq x_i, y_i \leq 10^3\);
- 25% test: \(1 \leq n \leq 10^3\), \(-10^7 \leq x_1, y_1, x_2, y_2 \leq 10^7\), \(-10^7 \leq x_i, y_i \leq 10^7\);
- 25% test: \(1 \leq n \leq 10^5\), \(-10^3 \leq x_1, y_1, x_2, y_2 \leq 10^3\), \(-10^3 \leq x_i, y_i \leq 10^3\);
- 25% test còn lại: như ràng buộc trong đề bài.
Nhận xét