Elearning CodePath – CTP Online Judge

Va Chạm Đảo

TP003

🟢 Medium #Graph #Math #Binary Search #Two Pointers

### 📌 Thông tin chung

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

Cho $N$ hòn đảo, đảo thứ $i$ có tâm tại tọa độ $(x_i, y_i)$.

**Hình dạng và Sự bồi đắp:**
* Ban đầu (Tháng 0): Mỗi đảo là một hình vuông có tâm tại $(x_i, y_i)$ và chiều dài cạnh là $2$. Kích thước hình vuông ban đầu được xác định bởi: $|x - x_i| \le 1$ và $|y - y_i| \le 1$.
* Sau mỗi tháng, đảo thứ $i$ được bồi đắp (mở rộng về 4 hướng) thêm $R_t$ mét, trong đó $R_t \in \{1, 2\}$ là tốc độ mở rộng trong tháng $t$.

Gọi $L_t$ là **tổng độ mở rộng** sau $t$ tháng, $L_t = \sum_{m=1}^{t} R_m$.
* Kích thước của đảo $i$ sau $t$ tháng là hình vuông có tâm $(x_i, y_i)$ và chiều dài cạnh $2(1 + L_t)$.
* Tọa độ của đảo $i$ sau $t$ tháng là: $|x - x_i| \le 1 + L_t$ và $|y - y_i| \le 1 + L_t$.

**Va chạm:** Hai đảo $i$ và $j$ được xem là va chạm nếu chúng **chạm nhau** (kể cả cạnh hoặc đỉnh). Va chạm xảy ra khi tổng khoảng cách tối thiểu giữa chúng (theo trục $x$ hoặc $y$) bằng 0.

**Điều kiện va chạm giữa hai hình vuông tâm $(x_i, y_i)$ và $(x_j, y_j)$ sau $t$ tháng:**
Khoảng cách theo trục $x$ giữa tâm hai hình vuông là $|x_i - x_j|$. Kích thước (bán kính) mở rộng của mỗi hình vuông là $1 + L_t$.
Va chạm xảy ra khi tổng các kích thước mở rộng $\ge$ khoảng cách giữa hai tâm (theo trục $x$ **hoặc** trục $y$).
$2 \times (1 + L_t) \ge \min(|x_i - x_j|, |y_i - y_j|)$
Đặt $D_{i,j} = \min(|x_i - x_j|, |y_i - y_j|)$. Va chạm xảy ra khi:
$1 + L_t \ge \frac{D_{i,j}}{2}$

Yêu cầu: Tìm **tháng $t$ nhỏ nhất** ($1 \le t \le K$) mà sau khi bồi đắp, xảy ra ít nhất một sự va chạm giữa hai đảo bất kỳ. Nếu sau $K$ tháng không có va chạm, kết quả là $-1$.

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

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

* Dòng 1: Hai số nguyên $N$ và $K$.
* $N$ dòng tiếp theo: Mỗi dòng chứa hai số $x_i$ và $y_i$.
* Dòng cuối cùng: Một dãy $K$ ký tự ('1' hoặc '2') mô tả tốc độ mở rộng $R_t$ cho $K$ tháng.

Giới hạn:
* $2 \le N \le 200$.
* $1 \le K \le 100,000$.
* $-10^9 \le x_i, y_i \le 10^9$.

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

Ghi ra file `LADA.OUT` một số nguyên: tháng va chạm sớm nhất, hoặc $-1$ nếu không có va chạm sau $K$ tháng.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 50, K \le 100$ | $30\%$ |
| 2 | $N \le 200, K \le 100,000$ | $70\%$ |

---

✅ Đã AC: 0 / 0 submissions