Elearning CodePath – CTP Online Judge

Đếm Số Vùng Đường Tròn

CIRCLE_AREA_COUNTING

🟢 Hard #Hash #Math

### 📌 Thông tin chung

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

Cho $N$ đường tròn phân biệt $\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_N$ cùng thuộc một mặt phẳng. Các đường tròn này có tâm nằm trên trục $Ox$.

Mỗi đường tròn $\mathcal{C}_i$ được định nghĩa bởi tọa độ tâm $x_i$ và bán kính $r_i$.

Điều kiện ràng buộc:
1. Hai đường tròn bất kỳ chỉ có **tối đa 1 điểm chung**. Điều này loại trừ trường hợp hai đường tròn cắt nhau tại 2 điểm, mà chỉ cho phép chúng tiếp xúc ngoài hoặc tiếp xúc trong, hoặc không giao nhau.
2. Các đường tròn là **phân biệt**.

Yêu cầu: Đếm xem có bao nhiêu vùng (khu vực) được chia ra bởi các đường tròn này trên mặt phẳng.

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

* Dòng đầu tiên: Số nguyên dương $N$ ($1 \le N \le 100000$).
* $N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $x_i$ và $r_i$ (tâm và bán kính).

Giới hạn: $|x_i| \le 10^9$, $1 \le r_i \le 10^9$.

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

In ra một số nguyên dương duy nhất là số lượng vùng.

---
### ✨ Ví dụ

| Input (`area.inp`) | Output (`area.out`) |
| :--- | :--- |
| `2` <br> `1 3` <br> `2 1` | `3` |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- | 
| 1 | $N \le 10^5$, mỗi đường tròn chỉ có tối đa 1 đường tròn con | $60\%$ | 
| 2 | $N \le 10^5$, không ràng buộc thêm | $40\%$ |

✅ Đã AC: 0 / 11 submissions