Elearning CodePath – CTP Online Judge

Kiểm tra các điểm thẳng hàng

COLLINEAR

🟢 Hard #Geometry

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Yêu cầu

Cho một tập hợp gồm $N$ điểm toạ độ trong mặt phẳng. 
Nhiệm vụ là kiểm tra xem liệu một đường thẳng duy nhất có thể được tạo thành đi qua tất cả các điểm này hay không (tức là kiểm tra tính thẳng hàng của $N$ điểm).

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

Kiểm tra xem tất cả $N$ điểm đã cho có thẳng hàng hay không.

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

* Dòng đầu tiên chứa số nguyên $T$ là số lượng bộ test ($1 \le T \le 20$).
* Mỗi bộ test có cấu trúc:
    * Dòng đầu tiên chứa số nguyên $N$ (số lượng điểm, $2 \le N \le 10^5$).
    * $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ là toạ độ của điểm thứ $i$.

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

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

Kết quả mỗi bộ test được in trên một dòng riêng biệt.
* In ra **"Yes"** nếu tất cả các điểm thẳng hàng.
* In ra **"No"** nếu các điểm không thẳng hàng.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `2` `3` `0 0` `1 1` `2 2` `2` `0 1` `2 0` | `Yes` `Yes` |

**Giải thích Ví dụ 1:**
Điểm $(0, 0), (1, 1), (2, 2)$. Độ dốc giữa mọi cặp điểm là $\frac{\Delta y}{\Delta x} = 1$. Thẳng hàng.

**Giải thích Ví dụ 2:**
Hai điểm luôn thẳng hàng.

---
### 🏷 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: 6 / 18 submissions