Đường quét
Ở 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.
Cách làm chung
Phần tiêu đề “Cách làm chung”- Đổ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.
- 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”).
- Đ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 x | Hình đang cắt | Khoảng y được phủ | Chiều dài | Diện tích dải |
|---|---|---|---|---|
| 0 đến 2 | hình 1 | [0, 2] | 2 | 2 × 2 = 4 |
| 2 đến 4 | hình 1, hình 2 | [0, 2] hợp [1, 4] = [0, 4] | 4 | 2 × 4 = 8 |
| 4 đến 6 | hình 2 | [1, 4] | 3 | 2 × 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#include <iostream>#include <vector>#include <algorithm>using namespace std;
// Tổng chiều dài phần hợp của các khoảng [a, b] trên một trục.long long doDaiHop(vector<pair<long long, long long>> khoang) { sort(khoang.begin(), khoang.end()); long long tong = 0, dau = 0, cuoi = 0; bool coKhoi = false; for (auto [a, b] : khoang) { if (!coKhoi || a > cuoi) { // khoảng mới tách rời khối đang gộp if (coKhoi) tong += cuoi - dau; dau = a; cuoi = b; coKhoi = true; } else cuoi = max(cuoi, b); } if (coKhoi) tong += cuoi - dau; return tong;}
struct Hinh { long long x1, y1, x2, y2; };
long long dienTichHop(const vector<Hinh> &hinh) { vector<long long> xs; for (auto &h : hinh) { xs.push_back(h.x1); xs.push_back(h.x2); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); long long dienTich = 0; for (size_t i = 0; i + 1 < xs.size(); i++) { vector<pair<long long, long long>> dangCat; for (auto &h : hinh) if (h.x1 <= xs[i] && xs[i + 1] <= h.x2) dangCat.push_back({h.y1, h.y2}); dienTich += (xs[i + 1] - xs[i]) * doDaiHop(dangCat); } return dienTich;}
int main() { cout << dienTichHop({{0, 0, 4, 2}, {2, 1, 6, 4}}) << '\n'; // 18 return 0;}Ví dụ: cặp điểm gần nhất
Phần tiêu đề “Ví dụ: cặp điểm gần nhất”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).
Luyện tập
Phần tiêu đề “Luyện tập”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ố.
Nhóm 1. Sự kiện trên trục số
Phần tiêu đề “Nhóm 1. Sự kiện trên trục số”Bài 1. Lúc đông người nhất
Phần tiêu đề “Bài 1. Lúc đông người nhất”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ập | In ra |
|---|---|
41 52 44 76 8 | 2 |
Kiểm tra: nhập
60 103 66 95 79 121 4Bài 2. Tổng chiều dài được phủ
Phần tiêu đề “Bài 2. Tổng chiều dài được phủ”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ập | In ra |
|---|---|
41 32 57 98 10 | 7 |
Kiểm tra: nhập
60 410 123 66 815 2011 13Bài 3. Số cặp đoạn giao nhau
Phần tiêu đề “Bài 3. Số cặp đoạn giao nhau”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ập | In ra |
|---|---|
41 32 55 67 8 | 2 |
Kiểm tra: nhập
60 41 23 94 410 129 11Nhóm 2. Hình chữ nhật
Phần tiêu đề “Nhóm 2. Hình chữ nhật”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ập | In ra |
|---|---|
20 0 4 22 1 6 4 | 18 |
Kiểm tra: nhập
41 1 5 53 3 8 62 4 4 96 0 7 10Bài 5. Ô bị phủ nhiều lớp nhất
Phần tiêu đề “Bài 5. Ô bị phủ nhiều lớp nhất”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ập | In ra |
|---|---|
30 0 4 42 2 6 63 0 5 3 | 3 |
Kiểm tra: nhập
50 0 10 102 2 5 54 4 8 84 0 6 101 3 9 5Bài 6. Đếm điểm trong hình chữ nhật
Phần tiêu đề “Bài 6. Đếm điểm trong hình chữ nhật”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ập | In ra |
|---|---|
5 31 12 34 23 55 51 1 3 32 2 5 50 4 2 9 | 240 |
Kiểm tra: nhập
8 40 02 73 35 16 67 28 84 40 0 4 43 1 7 65 5 9 91 2 2 3Nhóm 3. Điểm và đoạn thẳng
Phần tiêu đề “Nhóm 3. Điểm và đoạn thẳng”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ập | In ra |
|---|---|
40 2 6 21 0 1 54 1 4 27 0 7 3 | 2 |
Kiểm tra: nhập
60 1 8 10 4 5 42 0 2 65 3 5 96 0 6 19 0 9 9Bài 8. Cặp điểm gần nhất
Phần tiêu đề “Bài 8. Cặp điểm gần nhất”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ập | In ra |
|---|---|
50 05 53 49 14 6 | 2 |
Kiểm tra: nhập
810 10-3 72 28 -1-5 -56 40 93 -2Bà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ập | In ra |
|---|---|
30 4 32 6 55 9 2 | 32 |
Kiểm tra: nhập
51 5 102 4 123 9 68 12 913 15 1