Elearning CodePath – CTP Online Judge

Đếm Đoạn Thẳng Chia Đều

GEN007

🟢 Hard #Sorting #Binary Search #Two Pointers

### 📌 Thông tin chung

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

Trên trục tọa độ $Ox$, cho $N$ điểm khác nhau $P_1, P_2, \dots, P_N$, với tọa độ tương ứng là $x_1, x_2, \dots, x_N$.

Một đoạn thẳng $AB$ được gọi là **đoạn thẳng chia đều** nếu nó được xác định bởi ba điểm đã cho $A, B, M$ sao cho $M$ là trung điểm của đoạn thẳng $AB$.

Giả sử $A, B, M$ có tọa độ lần lượt là $x_A, x_B, x_M$. Điều kiện $M$ là trung điểm của $AB$ được biểu diễn bằng công thức:
$x_M = \frac{x_A + x_B}{2}$
Trong đó $x_A, x_B, x_M$ là các tọa độ lấy từ tập hợp $\{x_1, x_2, \dots, x_N\}$.

Yêu cầu: Tính số lượng các bộ ba **không có thứ tự** $\{A, B, M\}$ khác nhau thỏa mãn điều kiện đoạn thẳng chia đều.

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

Dữ liệu vào từ file `CHIADEU.INP`:

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên $x_1, x_2, \dots, x_N$ cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 10^5$ (Nếu $N=10^5$, thuật toán $O(N^2)$ là quá chậm. Ta sẽ dùng $N \le 1000$ cho Subtask 1).
* $|x_i| \le 10^5$.

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

Ghi ra file `CHIADEU.OUT` một số nguyên duy nhất là kết quả tìm được.

---
### ✨ Ví dụ

| Input (`CHIADEU.INP`) | Output (`CHIADEU.OUT`) |
| :--- | :--- |
| `5` <br> `3 -1 2 5 4` | `3` |

Giải thích: Tập tọa độ $S = \{-1, 2, 3, 4, 5\}$.
* Cặp $(-1, 5)$: Tổng 4. Trung điểm $x_M = 2$. $2 \in S$. (Đoạn 1: $\{-1, 5, 2\}$)
* Cặp $(2, 4)$: Tổng 6. Trung điểm $x_M = 3$. $3 \in S$. (Đoạn 2: $\{2, 4, 3\}$)
* Cặp $(3, 5)$: Tổng 8. Trung điểm $x_M = 4$. $4 \in S$. (Đoạn 3: $\{3, 5, 4\}$)
* Cặp $(-1, 3)$: Tổng 2. Trung điểm $x_M = 1$. $1 \notin S$.
* ... và các cặp khác không thỏa mãn.
* Tổng cộng: 3 đoạn.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 6 submissions