Elearning CodePath – CTP Online Judge

MINLINES

🟢 Hard #Combinatorics #Geometry

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho $N$ điểm trong không gian 2 chiều. 
Yêu cầu: Tìm số lượng đường thẳng tối thiểu cần thiết để đi qua tất cả $N$ điểm đã cho, với điều kiện mỗi đường thẳng này đều phải đi qua một điểm cố định là $(x_0, y_0)$.

---
### 📥 Định dạng Đầu vào

* Dòng đầu tiên chứa ba số nguyên $N, x_0, y_0$: số lượng điểm và tọa độ điểm cố định mà tất cả các đường thẳng phải đi qua.
* $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ là tọa độ của điểm thứ $i$.

Giới hạn:
* $1 \le N \le 10^5$.
* Tọa độ $|x_i|, |y_i|, |x_0|, |y_0| \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra một số nguyên là số lượng đường thẳng tối thiểu cần tìm.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5 1 0` `-1 3` `4 3` `2 1` `-1 -2` `3 -3` | `2` |

**Giải thích Ví dụ:**
$N=5$, điểm cố định $(x_0, y_0) = (1, 0)$.
Ta cần vẽ ít nhất hai đường thẳng đi qua $(1, 0)$ để bao phủ tất cả các điểm:
* Đường thứ nhất đi qua $(-1, 3)$, $(4, 3)$.
* Đường thứ hai đi qua $(2, 1)$, $(-1, -2)$, $(3, -3)$.

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc $N$ |  Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N \le 1000$| $30\%$ |
| $2$ | $N \le 10^5$| $70\%$ |

---

✅ Đã AC: 0 / 9 submissions