Đếm số lượng hình thoi có thể vẽ trong hình chữ nhật cho trước trong C++

Cho một hình chữ nhật với kích thước chiều cao height và chiều rộng width. Hình chữ nhật được biểu diễn trên hệ trục tọa độ 2D với góc dưới bên trái tại điểm (0,0). Mục tiêu là đếm số lượng hình thoi có thể vẽ bên trong hình chữ nhật này sao cho thỏa mãn các điều kiện:

• Hình thoi có diện tích lớn hơn 0.
• Hai đường chéo của hình thoi song song với trục x và trục y.
• Tất cả các đỉnh của hình thoi có tọa độ nguyên.

Ví dụ

Đầu vào: length = 3, width = 3
Đầu ra: 4
Giải thích: Có 4 hình thoi thỏa mãn điều kiện.

Đầu vào: length = 2, width = 3
Đầu ra: 2

Giải thuật

Hình thoi đầu tiên có diện tích khác 0 và tọa độ nguyên bắt đầu từ góc trên bên phải tại (2,2). Duyệt từ i = j = 2 đến i <= length và j <= width. Tăng i và j mỗi lần 2 đơn vị (để đảm bảo tọa độ nguyên). Số lượng hình thoi với các đường chéo này là (height - i + 1) × (width - j + 1).

• Nhận length và width là số nguyên.
• Hàm possible_rhombus(int height, int width) trả về số lượng hình thoi.
• Khởi tạo count = 0.
• Vòng lặp i từ 2 đến height, bước nhảy 2.
• Vòng lặp j từ 2 đến width, bước nhảy 2.
• Tính temp_1 = height - i + 1, temp_2 = width - j + 1.
• Cộng temp_1 * temp_2 vào count.
• Trả về count.

Ví dụ triển khai

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

long long possible_rhombus(int height, int width) {
    long long count = 0;
    for (int i = 2; i <= height; i += 2) {
        for (int j = 2; j <= width; j += 2) {
            int temp_1 = height - i + 1;
            int temp_2 = width - j + 1;
            count += temp_1 * temp_2;
        }
    }
    return count;
}

int main() {
    int height = 4, width = 4;
    cout << "Count of number of rhombi possible inside a rectangle of given size are: " << possible_rhombus(height, width);
    return 0;
}

Kết quả

Count of number of rhombi possible inside a rectangle of given size are: 16