Em đang làm bài này:
Cho trước N hình chữ nhật có các cạnh song song hoặc trùng với các trục tọa độ, tìm diện tích phần chung của các hình chữ nhật này.
Input:
- Dòng đầu là số N, là số lượng hình chữ nhật (1 <= N <= 5000)
- N dòng tiếp theo, mỗi dòng nhập 4 chỉ số x1, y1, x2, y2 đại diện cho tọa độ của đỉnh phía trên bên trái và đỉnh phía dưới bên phải
Output:
- Gồm 1 dòng duy nhất là diện tích hình chung của tất cả hình chữ nhật
Mọi người giúp em bài này ạ.
Em làm theo cách:
- Tạo một ma trận để đại diện cho mặt phẳng tọa độ, đánh số toàn bộ ma trận là 0
- Với mỗi hình chữ nhật nhập vào, thì trên mặt phẳng tọa độ (ma trận), ô nào chứa hình chữ nhật đó thì giá trị sẽ tăng lên 1
- Cứ như thế đến cuối
- Nếu N hình đều trùng nhau, thì trên ma trận sẽ có những ô chứa giá trị N và diện tích sẽ là số lượng ô có giá trị N (ví dụ cho 5 hình chữ nhật, nếu cả 5 đều trùng nhau thì diện tích hình chung sẽ là số lượng các ô chứa giá trị năm (do cứ mỗi lần thêm 1 hình thì giá trị ô đó lại tăng) )
- Nếu không có ô nào có giá trị N thì đưa ra số không (không có hình chung nên diện tích = 0)
Nhưng em lại nghĩ, cách này tốn thời gian:
- Đề không cho giới hạn độ lớn của hình => phải tạo mặt phẳng tọa độ (ma trận) càng to càng tốt (đi thi HSG thành phố nó cho độ lớn max là 10^32 đấy)
- Mà như thế thì khi Set up (Fill, nói chung là cho nó thành 0 hết) là tốn O(N^2) (do dùng 2 vòng for chạy hết ma trận nên em nghĩ là N^2, em chưa học cái này)
- Sau đó, ví dụ đề troll, cho luôn 5000 hình chữ nhật (max luôn), với độ lớn = độ lớn của ma trận (nghĩa là nguyên cái ma trận đó được coi như là 5000 hình, nhưng máy không biết nên vẫn phải quét 5000 lần), thế là ngồi nhìn nó chạy giống như hồi làm bài
The Knight's tour
Em thì lại nghĩ mình phải:
- Tìm 1 công thức hay quy luật nào đó mà chỉ cần tọa độ thôi là có thể tìm được hình chung.
- Tìm hình chung của 2 hình chữ nhật đầu (tạm gọi là G1)
- Tìm hình chung giữa
G1và hình thứ 3 (G2) - Rồi cứ thế thì ta sẽ có tọa độ hình chung của N hình
Cái lợi của cách này:
- Nhanh hơn hẳn cách kia (
nhanh hơnthôi nhé, không có nghĩa là nhanh đâu) - Trong lúc xét, nếu có trường hợp
G nào đókhông trùng với hình tiếp theo thì cứreturn 0luôn, khỏi xét nữa.
Thế nhưng em vẫn chưa tìm ra cách giải kiểu này
Mọi người có cách nào khác cách demo qua ma trận không? Giúp em với
@gio
anh cứ oánh bừa N retangle rồi area rồi corrdinate rồi parallel nó tự ra đấy chứ 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?