【C++】辺の比率が[a,b]の範囲内にある長方形の個数を数える方法

長方形の各辺の情報と、範囲を表す2つの変数 first と last が与えられたとき、「長さ ÷ 幅」で計算される辺の比率が [first, last] の範囲内に収まる長方形の個数を求めるのが本記事の目的です。

入力例1

rec[] = { { 200, 210 }, { 100, 50 }, { 300, 190}, {180, 200}, {300, 200}}
first = 1.0, last = 1.6

出力例1

辺の比率が範囲[a,b]内にある長方形の個数: 4

説明

比率が [1.0, 1.6] の範囲内にあるのは以下の4組です。

{200,210}, {300,190}, {180,200}, {300,200}

入力例2

rec[] = { { 10,20 }, { 30, 10 }, { 100, 500}, {900, 300}, {450, 90}}
first = 3.0, last = 4.0

出力例2

辺の比率が範囲[a,b]内にある長方形の個数: 2

説明

比率が [3.0, 4.0] の範囲内にあるのは以下の2組です。

{30,10}, {900,300}

アルゴリズムの考え方

この問題では、各長方形の辺を pair<int,int> 型の配列として受け取ります。そして、それぞれのペアについて「大きい方の値 ÷ 小さい方の値」を計算し、その結果が範囲 [first, last] 内に収まっているかどうかを判定します。条件を満たしていればカウントを1つ増やします。

• pair<int,int> 型の配列 rec[] を用意します。

• 範囲を定義するための2つの変数 first と last を用意します。

• 関数 ratio_sides(pair<int, int> rec[], int total, double first, double last) は、長方形の辺の情報を受け取り、辺の比率が範囲 [a,b] 内にある長方形の個数を返します。

• カウント用の変数 count を 0 で初期化します。

• for ループを使って i = 0 から i < total まで順に処理します。

• ペア rec[i] の大きい方の値を maxi = max(rec[i].first, rec[i].second) として取り出します。

• ペア rec[i] の小さい方の値を mini = min(rec[i].first, rec[i].second) として取り出します。

• 比率 average = maxi / mini を計算します。

• average が範囲 [first, last] 内の値であれば、count をインクリメントします。

• for ループが終わったら、結果として count を返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int ratio_sides(pair<int, int> rec[], int total, double first, double last){
    int count = 0;
    for (int i = 0; i < total; i++){
        double maxi = max(rec[i].first, rec[i].second);
        double mini = min(rec[i].first, rec[i].second);
        double average = maxi/mini;
        if (average >= first){
            if(average <= last){
                count++;
            }
        }
    }
    return count;
}
int main(){
    pair<int, int> rec[] = { { 200, 210 }, { 100, 50 }, { 300, 190}, {180, 200}, {300, 200}};
    int total = 5;
    double first = 1.0, last = 1.6;
    cout<<"辺の比率が範囲[a,b]内にある長方形の個数: "<<ratio_sides(rec, total, first, last);
    return 0;
}

出力結果

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

辺の比率が範囲[a,b]内にある長方形の個数: 4