C++で指定サイズの長方形内に作成できる菱形の個数を数える方法

問題の概要

高さ×幅の寸法をもつ長方形が与えられます。この長方形は2次元座標系上に配置されており、左下の頂点が原点 (0,0) に位置します。今回の目的は、次のすべての条件を満たす菱形がこの長方形内にいくつ作れるかを数えることです。

• 菱形の面積が0より大きいこと。
• 菱形の対角線がx軸およびy軸に平行であること。
• 菱形のすべての頂点が整数座標を持つこと。

入出力例

入力:縦=3、横=3

出力:指定サイズの長方形内に作れる菱形の個数:4

説明:下の図は縦3×横3の長方形です。面積が0より大きく、対角線が両軸に平行で、頂点が整数座標である菱形が4つ存在します。

1つ目 [ (1,0), (2,1), (1,2), (0,1) ]
2つ目 [ (2,0), (3,1), (2,2), (1,1) ]
3つ目 [ (2,1), (3,2), (2,3), (1,2) ]
4つ目 [ (1,1), (2,2), (1,3), (0,2) ]

入力:縦=2、横=3

出力:指定サイズの長方形内に作れる菱形の個数:2

説明:下の図は縦2×横3の長方形で、内部に2つの菱形が確認できます。

アルゴリズムの考え方

面積が0より大きく、頂点が整数座標となる最小の菱形は、対角線の長さがそれぞれ2のもので、右上の頂点 (2,2) から考え始められます。走査は i=j=2 から開始し、i≦高さ、j≦幅 の範囲でループします。i と j を2ずつ増加させることで対角線の長さを常に偶数に保ち、頂点が必ず整数座標になるようにします。このとき、対角線の長さが i と j である菱形の配置数は (高さ−i+1)×(幅−j+1) で求められます。

• 縦と横の寸法を整数として受け取ります。
• 関数 possible_rhombus(int height, int width) は、長方形の寸法を受け取り、条件を満たす菱形の個数を返します。
• カウントの初期値を0に設定します。
• i=2 から i≦高さ、j=2 から j≦幅 の範囲を二重ループで走査します。
• 各 i, j について temp_1 = 高さ−i+1、temp_2 = 幅−j+1 を計算します。
• temp_1 × temp_2 をカウントに加算します。
• i と j を2ずつ増やします(頂点を整数座標にするため)。
• 最終的にカウントを結果として返します。

C++実装例

#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<<"指定サイズの長方形内に作れる菱形の個数: "<<possible_rhombus(height, width);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

指定サイズの長方形内に作れる菱形の個数: 16

このアルゴリズムの計算量は O(高さ×幅) であり、与えられた長方形内にある条件を満たすすべての菱形を効率的に数えることができます。