Diện tích hình chữ nhật lớn nhất bằng cách chọn 4 cạnh từ mảng trong C++

Diện tích hình chữ nhật tính bằng tích hai cạnh kề. Hình chữ nhật có 4 cạnh với cặp cạnh đối diện bằng nhau. Do đó cần 2 cặp cạnh bằng nhau (length và breadth) để tạo thành hình chữ nhật.

Cho một mảng chứa các độ dài cạnh theo thứ tự ngẫu nhiên. Nhiệm vụ: tìm 2 cặp cạnh lớn nhất từ mảng để có diện tích hình chữ nhật lớn nhất có thể.

Ví dụ 1

Input

Arr[] = { 1, 2, 1, 3, 4, 4, 2, 3, 5, 7 }

Output – Diện tích lớn nhất: 12

Giải thích: Sắp xếp giảm dần: { 7, 5, 4, 4, 3, 3, 2, 2, 1, 1 }

2 cặp cạnh lớn nhất: (4,4) và (3,3) → Diện tích = 4 × 3 = 12

Ví dụ 2

Input

Arr[] = { 8, 2, 5, 3, 4, 9, 8, 3, 5, 7 }

Output – Diện tích lớn nhất: 40

Giải thích: Sắp xếp giảm dần: { 9, 8, 8, 7, 5, 5, 4, 3, 3, 2 }

2 cặp cạnh lớn nhất: (8,8) và (5,5) → Diện tích = 8 × 5 = 40

Thuật toán

1. Sắp xếp mảng theo thứ tự giảm dần.
2. Duyệt mảng để tìm các cặp cạnh bằng nhau (arr[i] == arr[i+1]).
3. Lấy 2 cặp đầu tiên tìm được (lớn nhất do đã sắp xếp giảm).
4. Tính tích 2 giá trị đó.

Ví dụ code

#include <iostream>
#include <algorithm>
using namespace std;

int maxArea(int arr[], int n) {
    // Sắp xếp giảm dần
    sort(arr, arr + n, greater<int>());
    
    int dim[2] = {0, 0};
    int j = 0;
    
    for (int i = 0; i < n - 1 && j < 2; i++) {
        if (arr[i] == arr[i + 1]) {
            dim[j++] = arr[i];
            i++; // Bỏ qua phần tử đã dùng
        }
    }
    
    return dim[0] * dim[1];
}

int main() {
    int arr[] = { 1, 8, 5, 1, 8, 2, 5, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Maximum area of rectangle: " << maxArea(arr, n) << endl;
    return 0;
}

Kết quả

Maximum area of rectangle: 40

Giải thích code: Mảng sau sắp xếp: {8, 8, 5, 5, 3, 2, 1, 1}. Cặp đầu: 8, cặp thứ hai: 5. Diện tích = 8 × 5 = 40.

Lưu ý: Nếu không đủ 2 cặp, hàm trả về 0 (cần xử lý thêm tùy yêu cầu bài toán).