1. Nhận xét

Mỗi cây có thể được tưới bởi vòi ~1~ hoặc vòi ~2~. Nếu ta đặt:

• ~d_1(i)~ = bình phương khoảng cách từ cây ~i~ đến vòi ~1~
• ~d_2(i)~ = bình phương khoảng cách từ cây ~i~ đến vòi ~2~

Khi chọn ~R_1, R_2~, cây ~i~ được tưới nếu: ~d_1(i) \le R_1^2~ hoặc ~d_2(i) \le R_2^2~.

Ta cần tối thiểu hóa: ~R_1^2 + R_2^2~.

Nhận xét quan trọng: đáp án chỉ phụ thuộc vào các giá trị ~d_1(i), d_2(i)~; không cần căn bậc hai.

2. Mô hình hoá bài toán

Chọn một tập cây ~S~ tưới bởi vòi ~1~, còn lại tưới bởi vòi ~2~.

Khi đó giá trị tối ưu tương ứng là:

• ~R_1^2 = \max_{i \in S} d_1(i)~ (hoặc ~0~ nếu ~S~ rỗng)
• ~R_2^2 = \max_{i \notin S} d_2(i)~ (hoặc ~0~ nếu phần bù rỗng)

Mục tiêu: ~\min_{S} \left(\max_{i \in S} d_1(i) + \max_{i \notin S} d_2(i)\right)~.

3. Ý tưởng then chốt

Sắp xếp các cây theo ~d_1~ tăng dần.

Giả sử ta quyết định những cây có ~d_1~ nhỏ nhất (một ~\text{prefix}~) sẽ thuộc ~S~ (tưới bởi vòi ~1~). Khi đó:

• ~R_1^2~ chính là ~d_1~ lớn nhất trong ~\text{prefix}~ đó.
• ~R_2^2~ là ~max d_2~ của phần ~\text{suffix}~ còn lại.

Nếu sắp xếp theo ~d_1~, thì mọi lựa chọn tối ưu đều có thể xét dưới dạng cắt tại một vị trí:

• tưới bằng vòi 1 cho ~[0..i]~
• tưới bằng vòi 2 cho ~[i+1..n-1]~

Chỉ cần thử tất cả vị trí cắt.

4. Thuật toán

Với mỗi test:

1. Với mỗi cây, tính:

• ~d_1 = (u-x_1)^2 + (v-y_1)^2~
• ~d_2 = (u-x_2)^2 + (v-y_2)^2~

1. Tạo mảng cặp ~(d_1, d_2)~, sắp xếp tăng theo ~d_1~.

2. Tính mảng suffix:

• ~sufMax[i] = \max d_2~ trên đoạn ~[i..n-1]~
• đặt ~sufMax[n] = 0~

1. Duyệt vị trí cắt:

• Trường hợp vòi 1 không tưới cây nào: đáp án ứng viên là ~sufMax[0]~.

• Với mỗi ~i~ ~(0..n-1)~:

  • ~R_1^2 = d_1[i]~
  • ~R_2^2 = sufMax[i+1]~
  • cập nhật đáp án: ~ans = min(ans, R_1^2 + R_2^2)~.

5. Độ phức tạp

• Tính khoảng cách: ~O(n)~
• Sắp xếp: ~O(n \log n)~
• Suffix + duyệt: ~O(n)~

Tổng: ~O(n \log n)~ mỗi test. Bộ nhớ: ~O(n)~.

6. Lưu ý cài đặt

• Tọa độ tới ~10^9~, nên bình phương tới ~10^{18}~, dùng long long là đủ; để an toàn khi nhân có thể dùng __int128.
• Không cần lấy căn ~(\sqrt{})~, làm việc trực tiếp với bình phương.