বৃত্ত ও আয়ত ওভারল্যাপ চেক করা C++-এ

সমস্যা বিবরণ

একটি বৃত্ত (ব্যাসার্ধ r, কেন্দ্র cx, cy) এবং একটি অক্ষ-সমান্তরাল আয়ত (নিচের বাম কোণ x1, y1, উপরের ডান কোণ x2, y2) দেওয়া আছে। বৃত্ত ও আয়ত একে অপরের সাথে ওভারল্যাপ করে কিনা তা নির্ধারণ করতে হবে।

অ্যালগরিদম

বৃত্তের কেন্দ্র থেকে আয়তের সবচেয়ে নিকটবর্তী বিন্দু খুঁজে বের করুন। সেই বিন্দু থেকে কেন্দ্রের দূরত্ব যদি ব্যাসার্ধের চেয়ে ছোট বা সমান হয়, তবে ওভারল্যাপ আছে।

ধাপসমূহ:

1. eval(a, b, c) ফাংশন: max(b, min(a, c)) রিটার্ন করে। এটি আয়তের সীমানার ভেতর একটি মান ক্ল্যাম্প (clamp) করে।
2. বৃত্তের কেন্দ্র (cx, cy) কে আয়তের সীমায় ক্ল্যাম্প করে নিকটবর্তী বিন্দু (cdx, cdy) বের করুন।
3. কেন্দ্র ও নিকটবর্তী বিন্দুর মধ্যে দূরত্বের বর্গ disSq = (cx-cdx)² + (cy-cdy)² হিসাব করুন।
4. যদি disSq <= r² হয়, তবে true রিটার্ন করুন, অন্যথায় false।

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); // আউটপুট: 1 (true)
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(1) — কনস্ট্যান্ট টাইম অপারেশন।
• স্থান জটিলতা: O(1) — অতিরিক্ত স্পেস ব্যবহার হয় না।