指定された点を覆う最適な長方形を見つけるC++プログラム

はじめに

この記事では、指定された点を覆う「最適な長方形」を見つけるためのC++プログラムについて詳しく解説します。

問題の概要

この問題では、ある点の座標 (x, y) と、長さと幅の比 l/b が与えられます。求めるのは、次の条件をすべて満たす長方形の座標です。

• 与えられた点を内部に含んでいること
• 寸法が指定された比率 l : b に従っていること

条件を満たす長方形が複数存在する場合は、その中心と与えられた点とのユークリッド距離が最も短いものを選択します。

アルゴリズムのアプローチ

この問題は、以下の手順で解くことができます。

1. 比率の最小化： 最大公約数（GCD）を用いて比率 l/b を約分します。
2. スケールの決定： 許容される2次元領域 (n, m) 内に収まるように、min(n/l, m/b) の値を計算します。
3. 座標の計算： 最初に (x, y) を長方形の中心であると仮定します。長さと幅の値をそれぞれ加減算することで、左下と右上の頂点座標を求めます。
4. 境界の補正： 座標が領域からはみ出す場合は、はみ出した分だけ長方形全体をシフトして調整します。

C++による実装例

#include <cmath>
#include <iostream>
using namespace std;
// 与えられた比率を最小化する（最大公約数を求める）
int greatest_div(int l, int b) {
    if (l == 0)
        return b;
    else
        return greatest_div(b % l, l);
}
// 座標を計算する関数
void calc_coordinates(int n, int m, int x, int y, int l, int b) {
    int k, div1;
    int x1, y1, x2, y2;
    div1 = greatest_div(l, b);
    l /= div1;
    b /= div1;
    k = min(n / l, m / b);
    // 与えられた点が存在する範囲を求める
    x1 = x - (k * l - k * l / 2);
    x2 = x + k * l / 2;
    y1 = y - (k * b - k * b / 2);
    y2 = y + k * b / 2;
    // 座標が範囲外に出た場合の補正
    if (x1 < 0){
        x2 -= x1;
        x1 = 0;
    }
    if (x2 > n){
        x1 -= x2 - n;
        x2 = n;
    }
    if (y1 < 0){
        y2 -= y1;
        y1 = 0;
    }
    if (y2 > m) {
        y1 -= y2 - m;
        y2 = m;
    }
    cout << "Coordinates : " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
}
int main() {
    int n = 50, m = 20, x = 10, y = 6, l = 4, b = 7;
    calc_coordinates(n, m, x, y, l, b);
    return 0;
}

出力結果

Coordinates : 6 0 14 14

コードの解説

greatest_div 関数は、ユークリッドの互除法を再帰的に適用して2つの整数の最大公約数を求めます。これにより、比率 l : b をこれ以上約分できない形まで簡略化できます。

calc_coordinates 関数では、まず約分後の比率をもとに k = min(n/l, m/b) を計算し、領域 (n, m) 内に収まる最大のスケールを決定します。続いて、点 (x, y) を中心と仮定して長方形の4つの頂点座標 (x1, y1, x2, y2) を算出します。最後に、各座標が範囲 [0, n] や [0, m] を超えていないかを確認し、超えている場合は長方形全体を平行移動させることで領域内に収まるよう補正しています。

このアルゴリズムの計算量は、最大公約数の計算が O(log(min(l, b)))、それ以外の処理が O(1) であるため、非常に効率的です。