โจทย์ปัญหา
ได้รับชุดพิกัดจุด (X[i], Y[i]) ให้หา สี่เหลี่ยมผืนผ้าขนาดเล็กที่สุด ที่ครอบจุดทั้งหมด โดยมีด้านขนานแกนพิกัด (Axis-Aligned)
ตัวอย่าง
Input: X = {4, 3, 6, 1, -1, 12}, Y = {4, 1, 10, 3, 7, -1}
Output: 4 มุมของสี่เหลี่ยม:
{-1, -1} // Bottom-Left (Xmin, Ymin)
{-1, 10} // Top-Left (Xmin, Ymax)
{12, 10} // Top-Right (Xmax, Ymax)
{12, -1} // Bottom-Right (Xmax, Ymin)
แนวคิดการแก้ปัญหา
สี่เหลี่ยม Axis-Aligned ที่ครอบจุดทั้งหมด กำหนดโดย:
Xmin= min(X[i])Xmax= max(X[i])Ymin= min(Y[i])Ymax= max(Y[i])
มุมทั้ง 4 คือการจับคู่ (Xmin/Xmax, Ymin/Ymax)
โค้ดตัวอย่าง (C++)
#include <bits/stdc++.h>
using namespace std;
void printRectangle(int X[], int Y[], int n) {
int Xmin = *min_element(X, X + n);
int Xmax = *max_element(X, X + n);
int Ymin = *min_element(Y, Y + n);
int Ymax = *max_element(Y, Y + n);
cout << "{" << Xmin << ", " << Ymin << "}" << endl; // Bottom-Left
cout << "{" << Xmin << ", " << Ymax << "}" << endl; // Top-Left
cout << "{" << Xmax << ", " << Ymax << "}" << endl; // Top-Right
cout << "{" << Xmax << ", " << Ymin << "}" << endl; // Bottom-Right
}
int main() {
int X[] = {4, 3, 6, 1, -1, 12};
int Y[] = {4, 1, 10, 3, 7, -1};
int n = sizeof(X) / sizeof(X[0]);
printRectangle(X, Y, n);
return 0;
}ผลลัพธ์
{-1, -1}
{-1, 10}
{12, 10}
{12, -1}Complexity Analysis
- Time: O(n) - หา Min/Max เดินครั้งเดียว
- Space: O(1)
คำอธิบายเพิ่มเติม
- นี่คือ Bounding Box หรือ Minimum Bounding Rectangle (MBR)
- ใช้ใน: Computer Graphics, GIS, Collision Detection, Spatial Indexing
- ขยายเป็น 3D: เพิ่ม Zmin, Zmax → Axis-Aligned Bounding Box (AABB)
- ถ้าต้องการ Rotated Rectangle (Minimum Area Rectangle) ใช้ Rotating Calipers บน Convex Hull
ฟังก์ชัน STL ที่ใช้
std::min_element,std::max_element(Header<algorithm>)- ทำงานกับ Pointer/Iterator ได้ทั้ง Array และ Vector
