ได้รับจุด (x,y) และอัตราส่วนความยาว/ความกว้าง = l/b หาสี่เหลี่ยมที่ครอบจุดนี้และมีอัตราส่วนตามกำหนด ถ้ามีหลายรูปเลือกที่มีระยะห่างจากศูนย์กลางยุคลิดไปยังจุดนั้นน้อยที่สุด
วิธีแก้: ลดรูปอัตราส่วน l/b หา min(n/l, m/b) เพื่ออยู่ในพื้นที่ (n,m) สมมติ (x,y) เป็นศูนย์กลาง ถ้าไม่ใช่ ปรับพิกัดโดยลบ/บวกครึ่งความยาวและครึ่งความกว้าง
ตัวอย่างโค้ด
#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, 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
