30/09/2018, 16:54

Tính diện tích hình chữ nhật chung

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:

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.

Cái lợi của cách này:

Nhanh hơn hẳn cách kia (nhanh hơn thô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 0 luôn, khỏi xét nữa.