Trong bài viết này, chúng ta sẽ thảo luận về một chương trình để tìm hình chữ nhật phù hợp nhất bao phủ một điểm đã cho.
Trong bài toán này, chúng ta được cung cấp cho chúng ta tọa độ của một điểm (x, y) và tỷ lệ chiều dài / chiều rộng =l / b (giả sử). Chúng ta phải tìm tọa độ của một hình chữ nhật có chứa điểm đã cho và kích thước của nó tuân theo tỷ lệ đã cho. Trong trường hợp có nhiều hình chữ nhật, chúng ta phải chọn hình chữ nhật có khoảng cách ngắn nhất giữa tâm euclid của nó và điểm đã cho.
Để giải quyết vấn đề này, đầu tiên chúng ta sẽ giảm thiểu tỷ số l / b. Sau đó, chúng tôi tìm giá trị min (n / l, m / b) để ở trong vùng (n, m) (không gian 2d cho phép). Trước hết, chúng ta hãy giả sử rằng (x, y) chỉ là tâm của hình chữ nhật của chúng ta. Nếu không, chúng tôi sẽ tìm tọa độ ban đầu bằng cách đồng thời trừ và cộng các giá trị của chiều dài và chiều rộng tương ứng.
Ví dụ
#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;
} Đầu ra
Coordinates : 6 0 14 14