Kiểm tra tròn và hình chữ nhật chồng lấp trong C++

Giới thiệu

Cho một đường tròn với bán kính r và tâm (xc, yc), cùng một hình chữ nhật trục tọa độ với góc dưới bên trái (x1, y1) và góc trên bên phải (x2, y2). Xác định xem đường tròn và hình chữ nhật có giao nhau (chồng lấp) hay không.

Ý tưởng giải pháp

Tìm điểm trên hình chữ nhật gần tâm đường tròn nhất. Nếu khoảng cách từ tâm đến điểm đó ≤ bán kính thì có giao nhau.

1. Điểm gần nhất trên cạnh ngang: cdx = clamp(cx, left, right).
2. Điểm gần nhất trên cạnh dọc: cdy = clamp(cy, bottom, top).
3. Tính bình phương khoảng cách: dx = cx - cdx, dy = cy - cdy, disSq = dx*dx + dy*dy.
4. So sánh với r*r.

Cài đặt 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)); // clamp
    }

    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 = (double)r * r;
        return disSq <= sqrRadius;
    }
};

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

Phân tích

• Độ phức tạp thời gian: O(1).
• Độ phức tạp không gian: O(1).

Hàm eval thực hiện clamping giá trị vào khoảng [b, c]. Đây là cách chuẩn để tìm điểm chiếu của tâm tròn lên hình chữ nhật.