Elearning CodePath – CTP Online Judge

Bán kính hình tròn chứa K điểm

GEN036

🟢 Hard #Sorting #Geometry

### Bài toán
Trong mặt phẳng tọa độ Oxy, cho một hình tròn có tâm đặt tại gốc tọa độ (0, 0). Cho danh sách gồm n điểm với tọa độ ($x_i, y_i$).
Yêu cầu: Hãy tìm bán kính tối thiểu R của hình tròn sao cho có ít nhất k điểm nằm trong hoặc nằm trên đường tròn đó. 
Kết quả đầu ra là bình phương của bán kính R (tức là $R^2$).

### Định dạng Đầu vào
Dữ liệu vào từ file CIRCLE.INP:
* Dòng đầu tiên chứa hai số nguyên n và k ($1 \le k \le n \le 10^5$).
* n dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$ ($|x_i|, |y_i| <= 10^9$) đại diện cho tọa độ của một điểm.

### Định dạng Đầu ra
Ghi ra file CIRCLE.OUT một số nguyên duy nhất là giá trị R^2 nhỏ nhất tìm được.

### Ví dụ
| Input | Output |
| :--- | :--- |
| 3 3 | 2 |
| 1 1 | |
| -1 -1 | |
| 1 -1 | |

Giải thích:
* n = 3, k = 3. 
* Bình phương khoảng cách từ các điểm tới tâm (0,0) lần lượt là: 
 $ (1^2 + 1^2) = 2; ((-1)^2 + (-1)^2) = 2; (1^2 + (-1)^2) = 2.$
* Để chứa ít nhất 3 điểm, bình phương bán kính $R^2$ phải tối thiểu bằng 2.

### Subtasks
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 |$ n \le 1000 $| 40% |
| 2 |$ n \le 10^5 $| 60% |

✅ Đã AC: 0 / 4 submissions