Hiểu bài toán

Bài toán yêu cầu tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong n điểm cho trước trên mặt phẳng Oxy. Khoảng cách Manhattan giữa hai điểm (x1, y1) và (x2, y2) được định nghĩa là |x1 - x2| + |y1 - y2|. Với n tối đa là 100, chúng ta cần tìm giá trị lớn nhất của biểu thức này trong tất cả các cặp điểm.

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

Cách Brute Force (Đối sánh mọi cặp)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int,int>> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].first >> pts[i].second;
    }

    int best = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int d = abs(pts[i].first - pts[j].first) + abs(pts[i].second - pts[j].second);
            best = max(best, d);
        }
    }
    cout << best;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là cách tiếp cận trực tiếp và đơn giản nhất. Ta duyệt qua tất cả các cặp điểm (i, j) với i < j, tính khoảng cách Manhattan giữa chúng và cập nhật giá trị lớn nhất. Với n <= 100, số cặp điểm là khoảng 5000, hoàn toàn chấp nhận được về mặt thời gian thực thi. Phương pháp này đảm bảo tìm ra đáp án đúng vì nó kiểm tra tất cả khả năng.

Cách Tối ưu hóa bằng biến đổi tọa độ (Rotation)

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

int main() {
    ios_base :: sync_with_stdio( false );
    cin.tie( NULL ); cout.tie( NULL );

    int n;
    cin >> n;

    vector<int> x( n+1 ), y( n+1 );
    for( int i = 1; i <= n; i ++ )
        cin >> x[i] >> y[i];

    int a = x[1] - y[1];
    int b = x[1] + y[1];
    int c = -x[1] + y[1];
    int d = -x[1] - y[1];

    int res = 0;
    for( int i = 2; i <= n; i ++ ) {

        res = max( res, -x[i] + y[i] + a );
        res = max( res, -x[i] - y[i] + b );
        res = max( res, x[i] - y[i] + c );
        res = max( res, x[i] + y[i] + d );

        a = max( a, x[i] - y[i] );
        b = max( b, x[i] + y[i] );
        c = max( c, -x[i] + y[i] );
        d = max( d, -x[i] - y[i] );
    }

    cout << res << "\n";
    return 0;
}

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

Phương pháp này dựa trên việc biến đổi công thức khoảng cách Manhattan. Để tính max(|x1-x2| + |y1-y2|), ta có thể xem xét 4 trường hợp của dấu. Ví dụ, max(|x1-x2| + |y1-y2|) tương đương với max( (x1+y1) - (x2+y2), (x1-y1) - (x2-y2), (-x1+y1) - (-x2+y2), (-x1-y1) - (-x2-y2) ). Do đó, khoảng cách lớn nhất là hiệu giữa giá trị lớn nhất và nhỏ nhất của các biểu thức (x+y), (x-y), (-x+y), (-x-y). Ta có thể duyệt qua các điểm, vừa đi vừa cập nhật giá trị lớn nhất/nhỏ nhất của 4 biểu thức này, và cập nhật kết quả. Cách này tối ưu hơn Brute Force về độ phức tạp tuyến tính O(n).

Cách Brute Force (Cơ bản với mảng)

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
unordered_map <ll,ll> mp;
int main()
{
    ll n,m=-1e6;
    cin>>n;ll a[n+10],b[n+10];
    for (ll i=1;i<=n;i++) cin>>a[i]>>b[i];
    for (ll i=1;i<=n-1;i++)
     for (ll j=i;j<=n;j++)
      m=max(abs(a[i]-a[j])+abs(b[i]-b[j]),m);
    cout<<m;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là biến thể của phương pháp Brute Force sử dụng mảng thường và kiểu dữ liệu long long. Logic vẫn là kiểm tra tất cả các cặp điểm. Tác giả sử dụng giá trị khởi tạo âm rất lớn (-1e6) cho biến lưu kết quả để đảm bảo nó được cập nhật chính xác ngay từ cặp đầu tiên.

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

Bài học kinh nghiệm

• Khoảng cách Manhattan có thể được tối ưu hóa từ O(n^2) xuống O(n) bằng cách sử dụng các biến đổi tọa độ (x+y, x-y). Max(|dx| + |dy|) = max( max(x+y) - min(x+y), max(x-y) - min(x-y) ).
• Với ràng buộc n <= 100, giải thuật O(n^2) (Brute Force) hoàn toàn đủ nhanh và dễ dàng cài đặt.

Lỗi thường gặp

• Sử dụng biến lưu kết quả với giá trị khởi tạo không đủ nhỏ (ví dụ 0) trong khi tất cả các khoảng cách có thể âm (mặc dù theo định nghĩa tuyệt đối thì khoảng cách luôn dương, nhưng logic so sánh max có thể sai nếu dùng min).
• Sai lệch trong vòng lặp duyệt cặp điểm (ví dụ j chạy từ i thay vì i+1) có thể dẫn đến việc tính khoảng cách của một điểm với chính nó (bằng 0) hoặc tính trùng lặp. Tuy nhiên, trong bài này không ảnh hưởng đến kết quả cuối cùng nhưng là thói quen xấu.