Editorial for hcnv2: Bài toán hình chữ nhật 2

Hiểu bài toán

Bài toán yêu cầu tính diện tích phần giao nhau của hai hình chữ nhật song song với trục tọa độ. Mỗi hình chữ nhật được đặc trưng bởi hai đỉnh đối diện. Do cách nhập không phân biệt đỉnh góc dưới-trái và đỉnh góc trên-phải, trước hết ta cần chuẩn hóa tọa độ để xác định khoảng tọa độ X và Y của mỗi hình. Sau đó, diện tích giao nhau được tính bằng cách tìm khoảng giao nhau trên trục X và trục Y. Nếu hai hình không giao nhau, diện tích bằng 0.

Các cách tiếp cận

Cách Tính toán trực tiếp

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
long long min(long long a,long long b){
return a<b ?a :b;}
long long max(long long a,long long b){
return a>b ?a :b;}

long long main(){
    long long x1,y1,x2,y2,x3,y3,x4,y4;
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
    long long xmin1=min(x1,x2);
    long long xmax1=max(x1,x2);
    long long ymin1=min(y1,y2);
    long long ymax1=max(y1,y2);
    long long xmin2=min(x3,x4);
    long long xmax2=max(x3,x4);
    long long ymin2=min(y3,y4);
    long long ymax2=max(y3,y4);
    long long left=max(xmin1,xmin2);
    long long right=min(xmax1,xmax2);
    long long top=min(ymax1,ymax2);
    long long bot=max(ymin1,ymin2);
    if (left>=right || bot>=top){
        printf("0");
        return 0;
    }
    else{
        printf("%lld",(top-bot)*(right-left));
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này xử lý trực tiếp dữ liệu đầu vào. Đầu tiên, xác định tọa độ tối thiểu và tối đa cho mỗi hình chữ nhật bằng hàm min/max. Giao nhau trên trục X nằm trong khoảng [max(xmin1, xmin2), min(xmax1, xmax2)], và tương tự cho trục Y. Nếu khoảng giao nhau hợp lệ (độ dài dương), diện tích là tích của hai độ dài này. Ngược lại, diện tích là 0.

Cách Sử dụng biến trung gian

#include <stdio.h>

long long min(long long a, long long b) {
    return (a < b) ? a : b;
}

long long max(long long a, long long b) {
    return (a > b) ? a : b;
}

int main() {
    long long x1, y1, x2, y2; 
    long long x3, y3, x4, y4; 

    scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
    scanf("%lld %lld %lld %lld", &x3, &y3, &x4, &y4);

    long long r1_min_x = min(x1, x2);
    long long r1_max_x = max(x1, x2);
    long long r1_min_y = min(y1, y2);
    long long r1_max_y = max(y1, y2);

    long long r2_min_x = min(x3, x4);
    long long r2_max_x = max(x3, x4);
    long long r2_min_y = min(y3, y4);
    long long r2_max_y = max(y3, y4);

    long long dx = min(r1_max_x, r2_max_x) - max(r1_min_x, r2_min_x);
    long long dy = min(r1_max_y, r2_max_y) - max(r1_min_y, r2_min_y);

    if (dx > 0 && dy > 0) {
        printf("%lld", dx * dy);
    } else {
        printf("0");
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này tương tự cách đầu tiên nhưng có thể tối ưu hóa việc kiểm tra điều kiện giao nhau. Thay vì tính toán các tọa độ biên rồi so sánh, ta tính trực tiếp độ dài của đoạn giao nhau trên mỗi trục. Nếu cả hai độ dài đều dương, ta nhân chúng lại. Nếu một trong hai bằng 0 (hoặc âm), diện tích bằng 0.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Việc chuẩn hóa tọa độ (biến đổi bất kỳ hai điểm đối diện thành điểm dưới-trái và trên-phải) là bước quan trọng nhất để đơn giản hóa bài toán.
• Diện tích giao nhau là một hình chữ nhật mới được xác định bởi các biên chung: cạnh trái là giá trị lớn nhất của các cạnh trái, cạnh phải là giá trị nhỏ nhất của các cạnh phải.

Lỗi thường gặp

• Quên kiểm tra trường hợp hai hình chữ nhật không giao nhau而导致 in ra số âm nếu dùng công thức trừ đơn giản không kiểm tra điều kiện.
• Sử dụng kiểu dữ liệu int thay vì long long có thể gây tràn số khi tính toán, do tọa độ có thể lên tới 10^8 (tích diện tích có thể lên tới 10^16).