特定の点をカバーする最適な長方形を見つけるためのC++プログラム

この記事では、特定のポイントをカバーする最適な長方形を見つけるプログラムについて説明します。

この問題では、点の座標（x、y）と長さ/幅の比率=l / b（たとえば）が与えられます。与えられた点を含み、その寸法が与えられた比率に従う長方形の座標を見つける必要があります。複数の長方形が存在する場合は、ユークリッドの中心と指定された点の間の距離が最も短い長方形を選択する必要があります。

これを解決するには、まず比率l/bを最小化します。その後、min（n / l、m / b）値が（n、m）領域（2次元スペースを許可）にとどまることがわかります。まず、（x、y）が長方形の中心のみであると仮定します。そうでない場合は、長さと幅の値をそれぞれ同時に減算および加算することにより、元の座標を見つけます。

例

#include <cmath>
#include <iostream>
using namespace std;
//to minimize the value of given ratio
int greatest_div(int l, int b) {
   if (l == 0)
      return b;
   else
      return greatest_div(b % l, l);
}
//to calculate the coordinates
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);
   //finding the range in which the given point exists
   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 the coordinates go out of the range
   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