Cho hai hình chữ nhật vuông góc trục tọa độ, mỗi hình xác định bởi góc dưới bên trái (A,B) và góc trên bên phải (C,D) cho hình 1, (E,F) và (G,H) cho hình 2. Tính diện tíchunion của chúng.
Ví dụ: A=-3,B=0,C=3,D=4, E=0,F=-1,G=9,H=2 → diện tích 45.
Giải thuật
- Tính diện tích mỗi hình: width1*height1 + width2*height2.
- Kiểm tra xem hai hình có giao nhau không: nếu GC hoặc F>D hoặc H
- Ngược lại, tính giao: p=max(A,E), q=max(B,F), r=min(C,G), s=min(D,H). Diện tích giao = (r-p)*(s-q).
- Trả về tổng diện tích - diện tích giao.
Ví dụ mã Python
def solve(A, B, C, D, E, F, G, H):
width_1 = abs(C - A)
height_1 = abs(D - B)
width_2 = abs(G - E)
height_2 = abs(H - F)
area = width_1 * height_1 + width_2 * height_2
if (G < A) or (E > C) or (F > D) or (H < B):
return area
else:
p = max(A, E)
q = max(B, F)
r = min(C, G)
s = min(D, H)
width_3 = abs(r - p)
height_3 = abs(s - q)
return area - (width_3 * height_3)
A, B, C, D = -3, 0, 3, 4
E, F, G, H = 0, -1, 9, 2
print(solve(A, B, C, D, E, F, G, H)) # Output: 45
Đầu vào
-3, 0, 3, 4, 0, -1, 9, 2
Đầu ra
45