Tìm hình chữ nhật tốt nhất bao phủ điểm cho trước C++

Cho điểm (x,y) và tỷ lệ cạnh l:b. Tìm hình chữ nhật (hcn) chứa điểm đó, cạnh theo tỷ lệ, và tâm hcn gần điểm nhất.

Giải pháp

• Rút gọn tỷ lệ l:b bằng UCLN.
• Tìm scale k = min(n/l, m/b) để hcn nằm trong vùng n×m.
• Đặt tâm hcn tại (x,y), tính tọa độ 4 góc.
• Nếu vượt ranh giới, dịch chuyển hcn về trong vùng.

Chương trình C++

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

void bestFitRect(int n, int m, int x, int y, int l, int b) {
    int g = gcd(l, b);
    l /= g; b /= g;
    
    int k = min(n / l, m / b);
    int L = k * l, B = k * b; // chiều dài, rộng thực tế
    
    // Tâm tại (x,y) → tính 4 góc
    int x1 = x - L/2;
    int y1 = y - B/2;
    int x2 = x + L - L/2;
    int y2 = y + B - B/2;
    
    // Điều chỉnh về trong vùng [0,n]×[0,m]
    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 << "Toa do hcn: (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")\n";
    cout << "Kich thuoc: " << L << " x " << B << "\n";
}

int main() {
    // Vùng 50x20, điểm (10,6), tỷ lệ 4:7
    bestFitRect(50, 20, 10, 6, 4, 7);
    return 0;
}

Kết quả

Toa do hcn: (6,0) (14,14)
Kich thuoc: 8 x 14

Tỷ lệ 4:7 = 8:14, tâm (10,7) gần điểm (10,6) nhất có thể.