Bỏ qua để đến nội dung

Đường quét

Mức độ: Nâng cao

Ở bài Rời rạc hóa, các đoạn thẳng trên trục số được xử lý bằng cách tưởng tượng một đường thẳng quét từ trái sang phải, chỉ dừng lại ở các tọa độ có sự kiện (một đoạn bắt đầu hoặc kết thúc). Bài này dùng cùng ý đó cho các bài trên mặt phẳng: hình chữ nhật, điểm, đoạn thẳng.

  1. Đổi mọi thứ thành sự kiện có tọa độ x: hình chữ nhật bắt đầu, kết thúc; một điểm; một câu hỏi.
  2. Sắp xếp sự kiện theo x. Nếu nhiều sự kiện cùng x, quyết định thứ tự xử lý cho đúng đề (ví dụ đoạn đóng thì “bắt đầu” trước “kết thúc”).
  3. Đi qua các sự kiện, giữ một cấu trúc mô tả những gì đường quét đang cắt (các khoảng y đang được phủ, các điểm đã đi qua…), cập nhật nó ở mỗi sự kiện.

Bài toán hai chiều trở thành một dãy bài toán một chiều trên đường quét.

Ví dụ: diện tích hợp các hình chữ nhật

Phần tiêu đề “Ví dụ: diện tích hợp các hình chữ nhật”

Cho n hình chữ nhật có cạnh song song trục tọa độ, hình thứ i phủ [x1, x2] × [y1, y2]. Tính diện tích phần mặt phẳng được phủ (phần chồng nhau chỉ tính một lần).

Đường quét dọc đi từ trái sang phải. Giữa hai tọa độ x liên tiếp có sự kiện, tập hình chữ nhật mà đường quét cắt không đổi, nên chiều dài phần bị phủ trên đường quét cũng không đổi. Diện tích của dải đó là (chiều rộng dải) × (chiều dài phủ trên đường quét).

Ví dụ 2 hình: [0, 4] × [0, 2] và [2, 6] × [1, 4].

Dải xHình đang cắtKhoảng y được phủChiều dàiDiện tích dải
0 đến 2hình 1[0, 2]22 × 2 = 4
2 đến 4hình 1, hình 2[0, 2] hợp [1, 4] = [0, 4]42 × 4 = 8
4 đến 6hình 2[1, 4]32 × 3 = 6

Tổng diện tích 4 + 8 + 6 = 18, đúng bằng 8 + 12 trừ phần chung [2, 4] × [1, 2] có diện tích 2.

Chiều dài phần phủ trên đường quét là bài hợp các đoạn trên một trục: sắp các khoảng y theo đầu trái rồi gộp. Có khoảng 2n dải, mỗi dải gộp không quá n khoảng, nên cả bài khoảng 2n2 log n bước, đủ cho n vài nghìn. Với n lớn hơn, thay việc gộp lại từ đầu bằng một cây phân đoạn trên các tọa độ y, mỗi sự kiện chỉ cập nhật log n nút.

def do_dai_hop(cac_khoang):
"""Tổng chiều dài phần hợp của các khoảng [a, b] trên một trục."""
tong = 0
dau = cuoi = None
for a, b in sorted(cac_khoang):
if cuoi is None or a > cuoi: # khoảng mới tách rời khối đang gộp
if cuoi is not None:
tong += cuoi - dau
dau, cuoi = a, b
else:
cuoi = max(cuoi, b)
if cuoi is not None:
tong += cuoi - dau
return tong
def dien_tich_hop(hinh):
"""hinh: danh sách (x1, y1, x2, y2). Diện tích phần được phủ."""
xs = sorted({x for x1, y1, x2, y2 in hinh for x in (x1, x2)})
dien_tich = 0
for xa, xb in zip(xs, xs[1:]):
dang_cat = [(y1, y2) for x1, y1, x2, y2 in hinh if x1 <= xa and xb <= x2]
dien_tich += (xb - xa) * do_dai_hop(dang_cat)
return dien_tich
print(dien_tich_hop([(0, 0, 4, 2), (2, 1, 6, 4)])) # 18

Cho n điểm, tìm khoảng cách nhỏ nhất giữa hai điểm. Thử mọi cặp mất khoảng n2/2 bước.

Sắp các điểm theo x, quét từ trái sang phải, giữ d là khoảng cách nhỏ nhất đã tìm được. Khi tới điểm P, chỉ những điểm cách P theo chiều x ít hơn d mới có thể cho khoảng cách nhỏ hơn d. Trong số đó, chỉ cần xét các điểm có y nằm trong [yP - d, yP + d]. Nên giữ các điểm “còn gần” trong một tập có thứ tự theo y:

  • điểm nào đã cách P theo x từ d trở lên thì bỏ khỏi tập (nó cũng sẽ xa mọi điểm sau P);
  • tìm trong tập các điểm có y trong [yP - d, yP + d], so khoảng cách với P, rồi thêm P vào tập.

Các điểm cần so nằm trong hình chữ nhật d × 2d bên trái P, mà mọi cặp điểm trong đó cách nhau ít nhất d, nên chỉ có vài điểm (không quá 8). Cả bài khoảng n log n bước (bài 8).

Gồm 9 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Có n khách (1 ≤ n ≤ 2 × 105), khách thứ i đến lúc ai và về lúc bi (0 ≤ ai nhỏ hơn bi ≤ 109); khách có mặt từ lúc ai đến trước lúc bi. Dòng đầu có n, n dòng sau mỗi dòng có ai, bi. In ra số khách có mặt cùng lúc nhiều nhất.

Ví dụ:

NhậpIn ra
4
1 5
2 4
4 7
6 8
2

Kiểm tra: nhập

6
0 10
3 6
6 9
5 7
9 12
1 4
Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Trên trục số có n đoạn (1 ≤ n ≤ 2 × 105), đoạn thứ i là [li, ri] với 0 ≤ li nhỏ hơn ri ≤ 109. Dòng đầu có n, n dòng sau mỗi dòng có li, ri. In ra tổng chiều dài phần trục số được ít nhất một đoạn phủ.

Ví dụ:

NhậpIn ra
4
1 3
2 5
7 9
8 10
7

Kiểm tra: nhập

6
0 4
10 12
3 6
6 8
15 20
11 13
Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Có n đoạn (1 ≤ n ≤ 2 × 105), đoạn thứ i là [li, ri] với 0 ≤ li ≤ ri ≤ 109 (tính cả hai đầu). Dòng đầu có n, n dòng sau mỗi dòng có li, ri. In ra số cặp đoạn có ít nhất một điểm chung.

Ví dụ:

NhậpIn ra
4
1 3
2 5
5 6
7 8
2

Kiểm tra: nhập

6
0 4
1 2
3 9
4 4
10 12
9 11
Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Diện tích hợp các hình chữ nhật

Phần tiêu đề “Bài 4. Diện tích hợp các hình chữ nhật”

Có n hình chữ nhật cạnh song song trục tọa độ (1 ≤ n ≤ 1000), hình thứ i phủ phần mặt phẳng từ x1 đến x2 theo chiều ngang và từ y1 đến y2 theo chiều dọc (0 ≤ x1 nhỏ hơn x2 ≤ 109, 0 ≤ y1 nhỏ hơn y2 ≤ 109). Dòng đầu có n, n dòng sau mỗi dòng có x1, y1, x2, y2. In ra diện tích phần mặt phẳng được phủ.

Ví dụ:

NhậpIn ra
2
0 0 4 2
2 1 6 4
18

Kiểm tra: nhập

4
1 1 5 5
3 3 8 6
2 4 4 9
6 0 7 10
Xem đáp số

41

Hướng dẫn giải chi tiết: liên hệ tác giả.

Mặt phẳng chia thành các ô vuông đơn vị, ô (x, y) là hình vuông từ x đến x + 1 và từ y đến y + 1. Có n tấm thảm hình chữ nhật (1 ≤ n ≤ 1000), tấm thứ i phủ các ô (x, y) với x1 ≤ x nhỏ hơn x2 và y1 ≤ y nhỏ hơn y2 (0 ≤ x1 nhỏ hơn x2 ≤ 109, 0 ≤ y1 nhỏ hơn y2 ≤ 109). Dòng đầu có n, n dòng sau mỗi dòng có x1, y1, x2, y2. In ra số tấm thảm nhiều nhất cùng phủ một ô.

Ví dụ:

NhậpIn ra
3
0 0 4 4
2 2 6 6
3 0 5 3
3

Kiểm tra: nhập

5
0 0 10 10
2 2 5 5
4 4 8 8
4 0 6 10
1 3 9 5
Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n, q (1 ≤ n, q ≤ 105), n dòng sau mỗi dòng là tọa độ x, y của một điểm, q dòng sau mỗi dòng có x1, y1, x2, y2 (x1 ≤ x2, y1 ≤ y2). Mọi tọa độ từ 0 đến 109. Với mỗi câu hỏi, in ra số điểm có x1 ≤ x ≤ x2 và y1 ≤ y ≤ y2.

Ví dụ:

NhậpIn ra
5 3
1 1
2 3
4 2
3 5
5 5
1 1 3 3
2 2 5 5
0 4 2 9
2
4
0

Kiểm tra: nhập

8 4
0 0
2 7
3 3
5 1
6 6
7 2
8 8
4 4
0 0 4 4
3 1 7 6
5 5 9 9
1 2 2 3
Xem đáp số
3
5
2
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Giao của đoạn ngang và đoạn dọc

Phần tiêu đề “Bài 7. Giao của đoạn ngang và đoạn dọc”

Có n đoạn thẳng (1 ≤ n ≤ 105), mỗi đoạn hoặc nằm ngang hoặc thẳng đứng. Dòng đầu có n, n dòng sau mỗi dòng có x1, y1, x2, y2 là hai đầu đoạn (0 ≤ tọa độ ≤ 109; đoạn ngang có y1 = y2 và x1 nhỏ hơn x2, đoạn dọc có x1 = x2 và y1 nhỏ hơn y2). In ra số cặp (đoạn ngang, đoạn dọc) có điểm chung (chạm đầu mút cũng tính).

Ví dụ:

NhậpIn ra
4
0 2 6 2
1 0 1 5
4 1 4 2
7 0 7 3
2

Kiểm tra: nhập

6
0 1 8 1
0 4 5 4
2 0 2 6
5 3 5 9
6 0 6 1
9 0 9 9
Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Dòng đầu có n (2 ≤ n ≤ 105), n dòng sau mỗi dòng là tọa độ nguyên x, y của một điểm (|x|, |y| ≤ 109, có thể có điểm trùng nhau). In ra bình phương khoảng cách nhỏ nhất giữa hai điểm.

Ví dụ:

NhậpIn ra
5
0 0
5 5
3 4
9 1
4 6
2

Kiểm tra: nhập

8
10 10
-3 7
2 2
8 -1
-5 -5
6 4
0 9
3 -2
Xem đáp số

13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Diện tích dưới đường chân trời

Phần tiêu đề “Bài 9. Diện tích dưới đường chân trời”

Trên một con phố có n tòa nhà (1 ≤ n ≤ 105), tòa thứ i nhìn từ xa là hình chữ nhật từ x = li đến x = ri, cao hi (0 ≤ li nhỏ hơn ri ≤ 109, 1 ≤ hi ≤ 109), đáy nằm trên mặt đất. Dòng đầu có n, n dòng sau mỗi dòng có li, ri, hi. In ra diện tích phần bị các tòa nhà che (phần chồng nhau tính một lần).

Ví dụ:

NhậpIn ra
3
0 4 3
2 6 5
5 9 2
32

Kiểm tra: nhập

5
1 5 10
2 4 12
3 9 6
8 12 9
13 15 1
Xem đáp số

100

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy