CTDL & giải thuật

Sweep Line: hợp diện tích hình chữ nhật

Bài toán hình học hai chiều thường khó vì các miền chồng nhau. Đường quét biến mặt phẳng thành chuỗi lát dọc, tại mỗi lát chỉ cần biết tổng độ dài y đang được phủ.

Biến mặt phẳng thành các lát dọc

Diện tích hợp của nhiều hình chữ nhật không thể lấy tổng diện tích riêng vì vùng chồng bị đếm nhiều lần. Sweep Line đi theo trục x. Giữa hai hoành độ sự kiện liên tiếp, tập hình đang hoạt động không đổi; diện tích lát bằng chiều rộng nhân tổng độ dài y được phủ.

Ý chính

Tại hoành độ x, phải cộng diện tích từ prevX tới x bằng trạng thái cũ, rồi mới áp dụng toàn bộ sự kiện ở x. Thứ tự ngược lại sẽ gán sai hình cho lát bên trái.

Sweep Line: Hợp [0, 2)×[0, 2) và [1, 3)×[1, 3) = 7 Mốc x = 0, 1, 2, 3 Lát [0, 1): phủ y ∈ [0, 2) → S = 2 Rộng 1 × độ dài phủ 2 Lát [1, 2): phủ y ∈ [0, 3) → S = 3 Không đếm lặp vùng giao [1, 2) Lát [2, 3): phủ y ∈ [1, 3) → S = 2 Tổng diện tích: 2 + 3 + 2 = 7
Sweep Line: 2 hình vuông giao nhau Lát 1: x ∈ [0, 1) Phủ y ∈ [0, 2) dài 2 → S = 2 Lát 2: x ∈ [1, 2) Phủ y ∈ [0, 3) dài 3 → S = 3 Lát 3: x ∈ [2, 3) Phủ y ∈ [1, 3) dài 2 → S = 2 Tổng diện tích = 2 + 3 + 2 = 7
Hình 1. Quét qua ba lát dọc x = 0..1, 1..2, 2..3 để tính diện tích hợp hai hình chữ nhật.

Tạo sự kiện từ hình chữ nhật

Mỗi hình [x1,x2) × [y1,y2) với x1 < x2, y1 < y2 (bề rộng và chiều cao > 0) tạo hai sự kiện: (x1,+1,y1,y2) mở vùng phủ và (x2,-1,y1,y2) đóng vùng. Dùng đoạn nửa mở giúp hai hình chỉ chạm cạnh không tạo diện tích giao.

Sắp mọi sự kiện theo x. Trước nhóm đầu, đặt prevX bằng x đầu và độ phủ bằng 0. Với mỗi x mới, cộng (x-prevX)*coveredY. Sau đó áp dụng tất cả sự kiện cùng x rồi gán prevX=x. Gom nhóm tránh trạng thái trung gian phụ thuộc thứ tự vào/ra tại cùng tọa độ.

Hai hình vuông [0,2)×[0,2) và [1,3)×[1,3) có diện tích riêng 4+4. Trên lát x từ 1 tới 2, hợp y dài 3 chứ không phải 4 vì khoảng [1,2) chồng nhau. Tổng ba lát là 2+3+2=7.

Vì sao phải nén tọa độ y?

Tọa độ có thể tới một tỷ, nhưng trạng thái phủ chỉ thay đổi tại y1 hoặc y2 của hình. Sắp các y phân biệt. Lá thứ i đại diện khoảng thật [ys[i],ys[i+1]), có độ dài ys[i+1]-ys[i]; không đại diện một điểm hay một đơn vị.

Đây là chỗ dễ sai khi nén: hạng liên tiếp không có nghĩa khoảng cách bằng 1. Cây phải cộng độ dài gốc từ mảng ys, không đếm số lá được phủ.

Cây phủ lưu cover và length

Mỗi nút lưu cover: số cập nhật phủ trọn nút, và length: tổng độ dài thật đang được phủ. Nếu cover>0, toàn đoạn nút được phủ nên length=ys[r]-ys[l]. Nếu cover=0 ở lá, length=0. Nếu cover=0 ở nút trong, length bằng tổng hai con.

Cập nhật một khoảng y tăng hoặc giảm cover trên các nút được phủ trọn. Hàm pull tính lại length theo ba trường hợp trên. Gốc luôn cho coveredY hiện tại trong O(1); mỗi sự kiện cập nhật O(log n).

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std; using ll=long long;
struct Seg{int n;vector<int>cover;vector<ll>len,ys;Seg(vector<ll> y):n(y.size()-1),cover(4*max(1,n)),len(4*max(1,n)),ys(move(y)){}void pull(int p,int l,int r){if(cover[p])len[p]=ys[r]-ys[l];else if(r-l==1)len[p]=0;else len[p]=len[p*2]+len[p*2+1];}void add(int ql,int qr,int v,int p,int l,int r){if(qr<=l||r<=ql)return;if(ql<=l&&r<=qr)cover[p]+=v;else{int m=(l+r)/2;add(ql,qr,v,p*2,l,m);add(ql,qr,v,p*2+1,m,r);}pull(p,l,r);}void add(int l,int r,int v){if(l<r)add(l,r,v,1,0,n);}ll total(){return n?len[1]:0;}};
ll union_area(const vector<tuple<ll,ll,ll,ll>>& rects){vector<ll>ys;vector<tuple<ll,int,ll,ll>>e;for(auto [x1,y1,x2,y2]:rects){ys.push_back(y1);ys.push_back(y2);e.push_back({x1,1,y1,y2});e.push_back({x2,-1,y1,y2});}if(e.empty())return 0;sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());sort(e.begin(),e.end());Seg st(ys);ll ans=0,prev=get<0>(e[0]);for(size_t i=0;i<e.size();){ll x=get<0>(e[i]);ans+=(x-prev)*st.total();while(i<e.size()&&get<0>(e[i])==x){auto [xx,v,y1,y2]=e[i++];int l=lower_bound(ys.begin(),ys.end(),y1)-ys.begin(),r=lower_bound(ys.begin(),ys.end(),y2)-ys.begin();st.add(l,r,v);}prev=x;}return ans;}
int main(){int n=2;vector<tuple<ll,ll,ll,ll>>r={{0,0,2,2},{1,1,3,3}};if(cin>>n){r.resize(n);for(auto&[a,b,c,d]:r)cin>>a>>b>>c>>d;}cout<<union_area(r)<<'\n';}

Bản C++17 dùng Segment Tree để đạt O(n log n). Bản Python đi qua các khoảng y đã nén sau mỗi sự kiện, đơn giản hơn để đọc và vẫn đúng, nhưng có thể tốn O(n²) ở trường hợp xấu. Hai bản cùng giải một bài toán nhưng khác cấu trúc giữ trạng thái theo trục y.

Miền số và hình không hợp lệ

Tích (x-prevX)*coveredY có thể lớn dù mỗi tọa độ vừa 32 bit. C++ dùng long long và hợp đồng giả định tổng diện tích không vượt miền 64 bit. Code mẫu mong x1 < x2, y1 < y2 (độ dài cạnh > 0); nếu dữ liệu có góc nhập ngược, cần chuẩn hóa hoặc loại hình rỗng trước khi tạo sự kiện.

Sự kiện rỗng không đóng góp nhưng có thể tạo cây với số lá 0. Hàm trả 0 ngay khi danh sách hình rỗng. Một hình duy nhất là ca tốt để kiểm nén có đúng hai mốc y và một lá.

Cẩn thận

Không cộng diện tích sau khi áp dụng sự kiện tại x. Trạng thái mới mô tả lát bên phải x, còn chiều rộng vừa đi qua nằm bên trái.

Đường quét còn dùng ở đâu?

Đếm giao giữa đoạn ngang và đứng: tạo sự kiện thêm đoạn ngang, hỏi tại x của đoạn đứng, rồi xóa; Fenwick lưu số đường ngang theo y. Bài điểm gần nhất quét theo x và giữ tập điểm có x đủ gần. Lịch phòng họp quét theo thời gian với sự kiện +1/-1 để lấy độ phủ lớn nhất.

Mỗi biến thể cần quyết định thứ tự sự kiện khi tọa độ bằng nhau. Với đoạn đóng, “thêm, hỏi, xóa” có thể cần thứ tự khác hình nửa mở. Không sao chép comparator mà chưa xác định hai đối tượng chạm biên có được tính hay không.

Tự kiểm tra bằng cách đếm ô đơn vị trên tọa độ nhỏ

Khi tọa độ nguyên nằm trong phạm vi nhỏ (chẳng hạn từ -10 đến 10), bạn có thể kiểm tra nhanh kết quả của đường quét bằng cách duyệt mọi ô đơn vị (x, y) nằm trong từng hình chữ nhật, đưa vào một set rồi đếm số ô phân biệt. Cách đếm trực tiếp này không dùng sự kiện, nén tọa độ hay cây phân đoạn, nên giúp phát hiện ngay lỗi lệch chỉ số lá ys[i + 1] - ys[i] hoặc cộng diện tích sai thời điểm.

Hãy thử đủ các trường hợp biên: hai hình giao nhau một phần, hai hình chỉ chạm cạnh, một hình nằm trọn trong hình kia, danh sách rỗng và các hình có tọa độ âm. Lưu ý rằng cách đếm ô đơn vị chỉ dùng để đối chiếu khi gỡ lỗi trên tọa độ nhỏ, vì số ô tăng theo tích độ lớn tọa độ chứ không theo số lượng hình chữ nhật.

Chạy tay ba lát của hai hình vuông

Hai hình [0,2)×[0,2) và [1,3)×[1,3) tạo các mốc x là 0,1,2,3. Trên ba lát liên tiếp, độ dài y được phủ là 2,3,2; diện tích cộng thêm lần lượt 2,3,2 và tổng bằng 7.

Tình huống Điều phải đúng
Hai hình chỉ chạm cạnh diện tích hợp bằng tổng riêng
Hai hình trùng hoàn toàn không nhân đôi diện tích
Một hình nằm trong hình khác kết quả bằng hình ngoài
Có tọa độ âm chênh lệch tọa độ vẫn dương đúng

Với tọa độ nguyên nhỏ, người học có thể đưa mọi ô đơn vị được phủ vào một set để lấy đáp án chậm. Đây là cách tự kiểm dễ hiểu; không dùng cho dữ liệu thật vì số ô tăng theo độ lớn tọa độ, không theo số hình.

Thứ tự sự kiện phụ thuộc định nghĩa biên

Trong bài diện tích với hình nửa mở, mọi sự kiện cùng x được gom sau khi cộng lát bên trái nên thứ tự nội bộ không ảnh hưởng. Trong bài đếm giao đoạn đóng, một đoạn đứng tại đúng đầu mút đoạn ngang có thể được tính; khi đó phải quy định “thêm trước, hỏi giữa, xóa sau”. Nếu đoạn mở, thứ tự có thể đảo.

Vì vậy comparator không phải chi tiết kỹ thuật có thể sao chép nguyên xi. Hãy viết một ca hai đối tượng chỉ chạm biên, quyết định đáp án bằng định nghĩa đề rồi thiết kế thứ tự sự kiện tạo đúng đáp án đó. Đây là cách tránh lỗi thường chỉ xuất hiện ở tọa độ bằng nhau.

Tính chu vi hợp hình chữ nhật cần nhiều thông tin hơn coveredY: số đoạn phủ rời nhau và trạng thái phủ ở hai đầu. Mỗi bước quét cộng phần ngang theo số thành phần, còn sự kiện làm thay đổi phần dọc. Cây phủ diện tích hiện tại chưa đủ cho biến thể này, nhưng nền tảng nén y và nhóm sự kiện vẫn giữ nguyên.

Bất biến của đường quét

Sau khi xử lý xong mọi sự kiện tại hoành độ x, cấu trúc trạng thái phải mô tả chính xác các đối tượng cắt đường thẳng ngay bên phải x. Viết câu này trước code sẽ quyết định thứ tự thêm, hỏi và xóa. Với đoạn đóng, điểm chạm biên được tính; với đoạn nửa mở, một đầu phải bị loại. Sai thứ tự sự kiện thực chất là làm hỏng bất biến này.

Luyện ngay trên Big-O Coding

Các bài dưới đây luyện đường quét với ba kiểu trạng thái khác nhau.

Bài đầu là đúng bài toán vừa học: diện tích hợp của N hình chữ nhật. Bài thứ hai luyện mô hình sự kiện với giao đoạn ngang–đứng, Fenwick đếm theo y. Bài thứ ba dùng đường quét cho cặp điểm gần nhất, trạng thái là tập có thứ tự thay vì cây phủ diện tích.

Câu hỏi thường gặp

Vì sao không dùng lưới 2D?

Tọa độ lớn làm lưới không khả thi. Đường quét chỉ xét các tọa độ nơi trạng thái thay đổi.

Có cần Segment Tree trong mọi sweep line?

Không. Tùy trạng thái có thể dùng Fenwick, multiset, heap hoặc chỉ một biến đếm.

Nén cả x có cần không?

Không cho bản quét này vì x được xử lý theo sự kiện sắp xếp. Ta vẫn dùng chênh lệch x thật giữa hai nhóm.

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483