Phủ điểm

Nguồn: CLUE OJ – Chương 11: Mảng 2 chiều Độ khó: Dễ Mảng 2 chiều Mảng đánh dấu Mảng hiệu 2 chiều

Đề bài

Cho $n$ hình chữ nhật nằm trên mặt phẳng Đề-các. Hình thứ $i$ có góc trái dưới là $(x_1, y_1)$, góc phải trên là $(x_2, y_2)$. Đếm số lượng điểm nằm trong ít nhất 1 hình chữ nhật.

Input:

• Dòng đầu tiên gồm 1 số nguyên $n$.
• $n$ dòng tiếp theo mỗi dòng gồm 4 số nguyên $x_1, y_1, x_2, y_2$.

Output: in ra số lượng điểm nằm trong ít nhất một hình chữ nhật.

Điều kiện: $1 \le n \le 100$; $1 \le x_1, y_1, x_2, y_2 \le 100$.

Ví dụ – input

2
1 1 2 2
1 1 3 3

Ví dụ – output

9

Giải thích ví dụ: "điểm" ở đây là điểm có toạ độ nguyên, và điểm nằm trên cạnh cũng tính là nằm trong hình. Hình $(1,1)$–$(3,3)$ chứa $3 \times 3 = 9$ điểm, hình $(1,1)$–$(2,2)$ (4 điểm) nằm gọn bên trong nó, nên đáp án là $9$ chứ không phải $9 + 4 = 13$.

Lời mở đầu

Đề không nói rõ "điểm" là gì, nhưng ví dụ cho biết ngay: hình $(1,1)$–$(3,3)$ có 9 điểm – đó là $3 \times 3$ điểm có toạ độ nguyên, tính cả các điểm trên cạnh (nếu là diện tích thì chỉ có $2 \times 2 = 4$). Toạ độ chỉ tới $100$ nên cả mặt phẳng cần quan tâm chỉ là một lưới $100 \times 100$ – vừa khít một mảng 2 chiều. Bài này là bản "nhẹ" của bài Phủ điểm 2 (toạ độ tới $10^5$, $n$ tới $1000$); mình sẽ giải bằng cách tô điểm trực tiếp, rồi giới thiệu mảng hiệu 2 chiều – kỹ thuật chính để sau này giải bản 2.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngĐánh dấuCách 1Tô từng điểmCách 2Mảng hiệu 2D

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không ghi subtask, nhưng bộ test chia rõ thành 2 mức:

Test	n	Toạ độ	Số test có hình suy biến	Đáp án
1 – 30	2 … 10	1 … 15	21/30	9 … 213
31 – 100	100 … 100	1 … 100	70/70	8 472 … 9 691

• Test 1 – 30: rất nhỏ, $2 \le n \le 10$, mọi toạ độ $\le 15$; test 1 chính là ví dụ của đề. Có 21 test chứa tổng cộng 38 hình suy biến (đoạn thẳng hoặc một điểm, $x_1 = x_2$ hoặc $y_1 = y_2$) – chỗ bắt lỗi ai quên rằng điểm trên cạnh cũng được tính.
• Test 31 – 100: đều có $n = 100$ hình, toạ độ trải khắp $[1, 100]$, mỗi test có từ 3 hình suy biến trở lên (trung bình khoảng 10). Các hình phủ gần kín lưới: đáp án từ 8 472 đến 9 691 trên tổng số $100 \times 100 = 10^4$ điểm.
• Mọi hình đều có $x_1 \le x_2$, $y_1 \le y_2$ (không có hình bị "lật"). Đáp án không vượt $10^4$ nên dùng int là đủ.

Mình tạm gọi 2 mức là "subtask" để so sánh. Với giới hạn nhỏ này, cả 2 cách bên dưới đều qua hết:

Mức	Điều kiện	Test	Cách 1	Cách 2
1	$n \le 10$, toạ độ $\le 15$	1 – 30	✔	✔
2	$n = 100$, toạ độ tới $100$	31 – 100	✔	✔

Ý tưởngĐánh dấu điểm, không cộng diện tích

Hình $(x_1, y_1)$–$(x_2, y_2)$ chứa đúng các điểm nguyên $(x, y)$ với $x_1 \le x \le x_2$ và $y_1 \le y \le y_2$, tức là $(x_2 - x_1 + 1) \cdot (y_2 - y_1 + 1)$ điểm. Nhưng các hình có thể chồng lên nhau, nên không thể cộng số điểm của từng hình lại. Thay vào đó:

Mảng đánh dấu

Dùng mảng phu[x][y] (ban đầu toàn false). Với mỗi hình, gán phu[x][y] = true cho mọi điểm của nó. Cuối cùng đếm số ô true. Một điểm bị nhiều hình phủ thì vẫn chỉ là một ô true, nên không bị đếm trùng.

Em nhập các hình (mỗi hình 4 số x1 y1 x2 y2, các hình cách nhau dấu phẩy, toạ độ $\le 12$) rồi bấm Tiếp để xem từng hình được tô. Điểm vòng cam là điểm đã được tô từ trước – nếu cộng diện tích thì chúng bị đếm 2 lần:

Các hình

Ví dụ nhanh:

Cách 1Tô từng điểm – O(n · C²)

Cài đặt trực tiếp ý tưởng trên. Gọi $C = 100$ là toạ độ lớn nhất: mỗi hình tô tối đa $C^2 = 10^4$ điểm, $n = 100$ hình là $10^6$ phép gán – quá nhẹ.

C++▶ Chạy tay từng dòng codeCách 1: tô true mọi điểm của từng hình rồi đếm số ô true.

Dữ liệu vào (stdin) – sửa thoải mái2 1 1 2 2 1 1 3 3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để chạy tay được, khung này đổi MAXC = 105 thành MAXC = 6 (toạ độ từ 1 đến 5). Ô xanh: điểm đã tô, ô tím: điểm của hình đang xét chưa tô.

1. Mảng phu khai báo toàn cục nên tự được khởi tạo bằng false. Mình đặt kích thước 105 cho dư một chút.
2. Hai vòng lặp tô dùng dấu <= (x <= x2, y <= y2) vì điểm trên cạnh cũng thuộc hình. Viết nhầm thành < là đang tính diện tích chứ không phải số điểm (xem phần "Cách sai" bên dưới).
3. Kết quả tối đa $100 \times 100 = 10^4$ nên int là đủ (ở Phủ điểm 2, đáp án tới gần $10^{10}$ thì phải dùng long long).
4. Bản Python tô cả đoạn y1..y2 của một cột bằng phép gán lát cắt cho nhanh.

Không gian$O(C^2)$ với $C = 100$

Thời gian$O(n \cdot C^2)$ – khoảng $10^6$ phép gán

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất 0.003 giây. Python đúng 100/100 test, test chậm nhất 0.027 giây.

Hai cách sai hay gặp

Sai 1 – cộng số điểm từng hình: s += (x2 - x1 + 1) * (y2 - y1 + 1). Bị đếm trùng phần chồng nhau, ngay ví dụ đã ra 13. Chạy thật: 0/100 test đúng.
Sai 2 – tính diện tích: tô các ô vuông đơn vị (x < x2, y < y2) như bài "diện tích hợp các hình chữ nhật". Ví dụ ra 4. Chạy thật: 0/100 test đúng.

Cách 2Mảng hiệu 2 chiều – O(n + C²)

Cách 1 tốn thời gian ở chỗ mỗi hình phải tô cả vùng. Với giới hạn bài này thì không sao, nhưng ở bài Phủ điểm 2 ta sẽ cần một kỹ thuật mạnh hơn: mảng hiệu 2 chiều. Muốn cộng $1$ cho mọi điểm của hình $[x_1, x_2] \times [y_1, y_2]$, chỉ cần sửa 4 góc:

Mảng hiệu 2 chiều

D[x1][y1]++; D[x1][y2+1]--; D[x2+1][y1]--; D[x2+1][y2+1]++;
Sau khi xử lý mọi hình, tính cộng dồn 2 chiều $D[x][y] \mathrel{+}$ $= D[x-1][y]$ $+ D[x][y-1] - D[x-1][y-1]$ thì $D[x][y]$ chính là số hình phủ điểm $(x, y)$. Đếm số điểm có $D[x][y] > 0$ là xong.

Vì sao 4 góc là đủ? Khi cộng dồn, giá trị $+1$ ở $(x_1, y_1)$ "lan" sang mọi điểm $(x, y)$ có $x \ge x_1, y \ge y_1$. Hai giá trị $-1$ ở $(x_1, y_2 + 1)$ và $(x_2 + 1, y_1)$ chặn sự lan đó phía trên hàng $y_2$ và bên phải cột $x_2$; vùng $x > x_2, y > y_2$ bị trừ 2 lần nên $+1$ ở $(x_2 + 1, y_2 + 1)$ bù lại. Kết quả: đúng các điểm của hình được cộng 1. Vì có chỉ số $x_2 + 1 \le 101$ nên mảng cần kích thước ít nhất $102$.

Em bấm Tiếp để xem 4 góc của từng hình được ghi vào mảng D, rồi cộng dồn ra số hình phủ từng điểm:

Các hình (tối đa 4, toạ độ ≤ 7)

Ví dụ nhanh:

C++▶ Chạy tay từng dòng codeCách 2: sửa 4 góc của mỗi hình trên mảng hiệu D, cộng dồn 2 chiều ra số hình phủ từng điểm.

Dữ liệu vào (stdin) – sửa thoải mái2 1 2 5 3 2 1 3 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung này dùng MAXC = 7 (toạ độ từ 1 đến 5, chỉ số x2 + 1 tối đa 6). Lúc cộng dồn: ô viền vàng là ô đang tính, 3 ô tím là 3 ô được dùng trong công thức.

Không gian$O(C^2)$

Thời gian$O(n + C^2)$

Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất 0.004 giây. Python đúng 100/100 test, test chậm nhất 0.026 giây.

Ưu điểm lớn của mảng hiệu là ta biết được số lần mỗi điểm bị phủ, nên đổi đề thành "đếm điểm bị phủ đúng $k$ lần" hay "ít nhất 2 lần" cũng chỉ cần sửa một điều kiện. Khi toạ độ lớn tới $10^5$ như Phủ điểm 2, mảng $10^5 \times 10^5$ không thể khai báo nổi; khi đó ta kết hợp mảng hiệu với nén toạ độ – các bạn đọc tiếp bài Phủ điểm 2 để thấy cách làm nhé.

Ghi chú của mình: mình đã chạy thật cả 2 cách (C++ và Python) trên đủ 100 test chính thức: tất cả đều đúng 100/100, test chậm nhất chưa tới 0.03 giây. Hai cách sai (cộng số điểm từng hình, và tính diện tích thay vì số điểm) đều đúng 0/100 và 0/100 – sai ngay từ test ví dụ. Mảng hiệu 2 chiều ở Cách 2 chính là nền tảng để giải bài Phủ điểm 2 khi toạ độ lên tới $10^5$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇