Editorial for minrect: Diện tích nhỏ nhất

Hiểu bài toán

Cho hai điểm A(x1, y1) và B(x2, y2) trên mặt phẳng Oxy với hoành độ và tung độ khác nhau. Yêu cầu tìm diện tích của hình chữ nhật có cạnh song song với trục tọa độ (cạnh nằm ngang và dựng đứng) sao cho hình chữ nhật đó là nhỏ nhất nhưng vẫn chứa cả hai điểm A và B. Do các cạnh phải song song với trục tọa độ, hình chữ nhật này được xác định bởi một hình chữ nhật có thể co gọn sao cho các cạnh của nó đi qua hai điểm này. Cạnh nằm ngang của hình chữ nhật có độ dài bằng khoảng cách giữa hai tung độ (|y1 - y2|), và cạnh nằm dọc có độ dài bằng khoảng cách giữa hai hoành độ (|x1 - x2|). Do đó, diện tích nhỏ nhất chính là tích của hai khoảng cách này.

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

Cách Sử dụng hàm ABS

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<abs(c-a)*abs(d-b);
}

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

Cách tiếp cận này là trực tiếp nhất. Sau khi nhập vào tọa độ của hai điểm, ta tính độ chênh lệch giữa hoành độ và tung độ. Vì diện tích là một đại lượng dương, ta cần lấy giá trị tuyệt đối của các hiệu này. Sau đó, nhân hai giá trị tuyệt đối đó lại để ra diện tích. Trong C++, hàm abs() trong thư viện <cstdlib> hoặc <cmath> (được bao gồm ngầm qua <bits/stdc++.h>) dùng để tính giá trị tuyệt đối. Biến được dùng là kiểu long (hoặc int) vì dữ liệu đầu vào nhỏ (0 ≤ x, y ≤ 100), nên không sợ tràn số.

Cách Sử dụng hàm llabs

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long width  = llabs(x1 - x2);
    long long height = llabs(y1 - y2);
    cout << (width * height);
    return 0;
}

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

Đây là biến thể của cách tiếp cận đầu tiên nhưng sử dụng kiểu dữ liệu 'long long' để lưu trữ tọa độ và kết quả. Hàm llabs() dùng để tính giá trị tuyệt đối cho kiểu long long. Cách này an toàn hơn nếu bài toán có giới hạn dữ liệu lớn hơn (ví dụ tọa độ lên tới 10^9), vì nó đảm bảo không bị tràn số khi tính toán. Tuy nhiên, với bài toán này, cách dùng long hay int đều thỏa mãn.

Cách Sử dụng std::abs

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    int di_1 = abs(x2 - x1), d2 =  abs(y2 - y1);
    int s = di_1 * d2;
    cout << s;
}

int main() {
    solve();
    return 0;
}

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

Cách tiếp cận này cũng thực hiện phép tính diện tích = |x1 - x2| * |y1 - y2|. Code được viết theo phong cách tổ chức hàm solve() và main() rõ ràng, thường thấy trong lập trình thi đấu. Nó sử dụng hàm abs() mặc định của C++ (thường là abs cho int). Việc khai báo 'using ll = long long;' trong code này không được sử dụng trực tiếp cho biến tọa độ (vì code dùng int), nhưng nó cho thấy thói quen khai báo kiểu dữ liệu dài cho các bài toán khác. Logic tính toán hoàn toàn giống với các cách trên.

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

Bài học kinh nghiệm

• Hình chữ nhật nhỏ nhất bao phủ hai điểm và có cạnh song song với trục tọa độ có diện tích chính là tích của khoảng cách giữa hai hoành độ và khoảng cách giữa hai tung độ.
• Diện tích luôn là một số dương, nên cần phải lấy giá trị tuyệt đối của hiệu tọa độ.

Lỗi thường gặp

• Quên lấy giá trị tuyệt đối khi tính hiệu tọa độ (ví dụ: x1 - x2 có thể âm), dẫn đến kết quả sai (hoặc lỗi biên nếu dùng số không dấu).
• Tràn số khi tính toán nếu dùng kiểu dữ liệu quá nhỏ (dù bài này dữ liệu nhỏ, nhưng nên quen dùng long long cho các bài toán tọa độ).