이 기사에서는 주어진 점을 덮는 가장 적합한 직사각형을 찾는 프로그램에 대해 논의할 것입니다.
이 문제에서 한 점의 좌표(x,y)와 길이/너비 =l/b(말하자면)의 비율이 제공됩니다. 주어진 점을 포함하고 치수가 주어진 비율을 따르는 직사각형의 좌표를 찾아야 합니다. 여러 개의 직사각형이 존재하는 경우 유클리드의 중심과 주어진 점 사이의 거리가 가장 짧은 것을 선택해야 합니다.
이를 해결하기 위해 먼저 비율 l/b를 최소화합니다. 그 후 min(n/l,m/b) 값이 (n,m) 영역(2d 공간 허용)에 머물도록 합니다. 먼저 (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