Giả sử chúng ta muốn tìm tổng diện tích được bao phủ bởi hai hình chữ nhật thẳng nằm trong một mặt phẳng 2D. Ở đây, mỗi hình chữ nhật được xác định bởi góc dưới cùng bên trái và góc trên cùng bên phải như trong hình.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu C =E hoặc A> =G hoặc B> =H hoặc D <=F, thì
-
return (C - A) * (D - B) + (G - E) * (H - F)
-
-
Xác định mảng h, chèn A, C, E, G vào h
-
Xác định một mảng v, chèn B, D, F, H vào v
-
sắp xếp mảng h và sắp xếp mảng v
-
tạm thời:=(h [2] - h [1]) * (v [2] - v [1])
-
tổng:=temp
-
tổng:=tổng + (C - A) * (D - B)
-
tổng:=tổng + (G - E) * (H - F)
-
tổng trả lại
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
if(C <= E || A >= G || B >= H || D <= F) return (C - A) * (D - B) + (G - E) * (H - F);
vector <int> h;
h.push_back(A);
h.push_back(C);
h.push_back(E);
h.push_back(G);
vector <int> v;
v.push_back(B);
v.push_back(D);
v.push_back(F);
v.push_back(H);
sort(h.begin(), h.end());
sort(v.begin(), v.end());
long long int temp = (h[2] - h[1]) * (v[2] - v[1]);
long long int total = - temp;
total += (C - A) * (D - B);
total += (G - E) * (H - F);
return total;
}
};
main(){
Solution ob;
cout << (ob.computeArea(-3, 0, 3, 4, 0, -1, 9, 2));
} Đầu vào
-3 0 3 4 0 -1 9 2
Đầu ra
45