การตรวจสอบการทับซ้อนของวงกลมและสี่เหลี่ยมผืนผ้าใน C++

ปัญหา: Circle and Rectangle Overlapping

กำหนดวงกลมด้วย (radius, xc, yc) โดย (xc, yc) คือศูนย์กลาง และสี่เหลี่ยมผืนผ้าที่ขนานแกน (axis-aligned) ด้วย (x1, y1, x2, y2) โดย (x1, y1) = มุมซ้ายล่าง, (x2, y2) = มุมขวาบน ตรวจสอบว่าทั้งสองรูปทับซ้อนกันหรือไม่

แนวคิดหลัก

หาจุดบนสี่เหลี่ยมที่อยู่ใกล้ศูนย์กลางวงกลมที่สุด (closest point) แล้วตรวจสอบระยะห่างจากจุดนั้นถึงศูนย์กลาง ว่าน้อยกว่าหรือเท่ากับรัศมีหรือไม่

ขั้นตอนการแก้

1. ฟังก์ชัน eval(a, b, c) – คืนค่า max(b, min(a, c)) ใช้ clamp ค่าระหว่าง b และ c
2. หาจุดใกล้ที่สุดบนสี่เหลี่ยม:
   • cdx = eval(cx, left, right) – พิกัด x ที่ clamp ระหว่าง left–right
   • cdy = eval(cy, bottom, top) – พิกัด y ที่ clamp ระหว่าง bottom–top
3. คำนวณระยะห่างยกกำลังสอง:
   • dx = cx - cdx, dy = cy - cdy
   • disSq = dx*dx + dy*dy
4. เปรียบเทียบกับ r*r – ถ้า disSq <= r*r → ทับซ้อน (true)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int eval(int a, int b, int c) {
        return max(b, min(a, c));
    }
    bool checkOverlap(int r, int cx, int cy,
                      int left, int bottom, int right, int top) {
        double cdx = eval(cx, left, right);
        double cdy = eval(cy, bottom, top);
        double dx = cx - cdx;
        double dy = cy - cdy;
        double disSq = dx * dx + dy * dy;
        double sqrRadius = r * r;
        return disSq <= sqrRadius;
    }
};

int main() {
    Solution ob;
    // r=1, center=(0,0), rect: left=1, bottom=-1, right=3, top=1
    cout << ob.checkOverlap(1, 0, 0, 1, -1, 3, 1); // Output: 1 (true)
    return 0;
}

อธิบายตัวอย่าง

วงกลมรัศมี 1 ศูนย์กลาง (0,0) สี่เหลี่ยมจาก (1,-1) ถึง (3,1)

• จุดบนสี่เหลี่ยมที่ใกล้ศูนย์กลางสุดคือ (1,0)
• ระยะห่าง = 1 → เท่ากับรัศมี → ทับซ้อนกัน

ความซับซ้อน

• เวลา: O(1) – คำนวณคงที่
• พื้นที่: O(1)

ข้อควรระวัง

• ใช้ double ป้องกัน overflow เมื่อคำนวณกำลังสอง
• ไม่ต้องแยกกรณีวงกลมอยู่ข้างใน/นอกสี่เหลี่ยม – สูตรครอบคลุมทุกกรณี
• กรณีขอบ (edge case): วงกลมสัมผัสขอบสี่เหลี่ยม → ถือว่าทับซ้อน