বৃত্ত-রেখা ছেদবিন্দু#

একটা বৃত্তের কেন্দ্রের স্থানাঙ্ক আর ব্যাসার্ধ, এবং একটা রেখার ইকুয়েশন দেওয়া আছে। তোমাকে ছেদবিন্দুগুলো বের করতে হবে।

সমাধান#

দুটো ইকুয়েশনের সিস্টেম সমাধান করার বদলে, আমরা সমস্যাটা জ্যামিতিকভাবে সমাধান করব। এতে নিউমেরিক্যাল স্ট্যাবিলিটির (numerical stability) দিক থেকে আরো সঠিক সমাধান পাওয়া যায়।

সাধারণতা না হারিয়ে আমরা ধরে নিচ্ছি বৃত্তের কেন্দ্র মূলবিন্দুতে। যদি না হয়, আমরা সেখানে সরাই এবং রেখার ইকুয়েশনে $C$ ধ্রুবক সংশোধন করি। তাই আমাদের $(0,0)$ কেন্দ্র ও $r$ ব্যাসার্ধের একটি বৃত্ত এবং $Ax+By+C=0$ ইকুয়েশনের একটি রেখা আছে।

চলো রেখার উপর মূলবিন্দুর নিকটতম বিন্দু $(x_0, y_0)$ খুঁজি। প্রথমত, এটা মূলবিন্দু থেকে নিচের দূরত্বে থাকতে হবে

$$ d_0 = \frac{|C|}{\sqrt{A^2+B^2}} $$

দ্বিতীয়ত, যেহেতু ভেক্টর $(A, B)$ রেখার সাথে লম্ব, বিন্দুর স্থানাঙ্ক এই ভেক্টরের স্থানাঙ্কের সমানুপাতিক হবে। যেহেতু আমরা মূলবিন্দু থেকে বিন্দুর দূরত্ব জানি, আমাদের কেবল $(A, B)$ ভেক্টরকে এই দৈর্ঘ্যে স্কেল করতে হবে, এবং আমরা পাব:

$$\begin{align} x_0 &= - \frac{AC}{A^2 + B^2} \\ y_0 &= - \frac{BC}{A^2 + B^2} \end{align}$$

ঋণাত্মক চিহ্নগুলো স্পষ্ট নয়, কিন্তু রেখার ইকুয়েশনে $x_0$ ও $y_0$ প্রতিস্থাপন করে সহজেই যাচাই করা যায়।

এই পর্যায়ে আমরা ছেদবিন্দুর সংখ্যা নির্ণয় করতে পারি, এবং এমনকি এক বা শূন্য বিন্দু হলে সমাধানও খুঁজতে পারি। আসলে, $(x_0, y_0)$ থেকে মূলবিন্দুর দূরত্ব $d_0$ যদি ব্যাসার্ধ $r$-র চেয়ে বড় হয়, উত্তর শূন্য বিন্দু। যদি $d_0=r$, উত্তর একটি বিন্দু $(x_0, y_0)$। যদি $d_0

তাহলে, আমরা জানি $(x_0, y_0)$ বিন্দুটি বৃত্তের ভিতরে। দুটি ছেদবিন্দু, $(a_x, a_y)$ ও $(b_x, b_y)$, অবশ্যই রেখা $Ax+By+C=0$-র উপর থাকবে এবং $(x_0, y_0)$ থেকে সমান দূরত্ব $d$-এ থাকবে, এবং এই দূরত্ব সহজেই বের করা যায়:

$$ d = \sqrt{r^2 - \frac{C^2}{A^2 + B^2}} $$

লক্ষ্য করো, ভেক্টর $(-B, A)$ রেখার সাথে সমরেখ। তাই $(x_0, y_0)$ বিন্দুতে $d$ দৈর্ঘ্যে স্কেল করা ভেক্টর $(-B,A)$ যোগ আর বিয়োগ করে আমরা চাওয়া বিন্দুগুলো পেতে পারি।

সবশেষে, দুটি ছেদবিন্দুর ইকুয়েশন:

$$\begin{align} m &= \sqrt{\frac{d^2}{A^2 + B^2}} \\ a_x &= x_0 + B \cdot m, a_y = y_0 - A \cdot m \\ b_x &= x_0 - B \cdot m, b_y = y_0 + A \cdot m \end{align}$$

আমরা যদি মূল ইকুয়েশন সিস্টেম বীজগণিতিক পদ্ধতিতে সমাধান করতাম, সম্ভবত ভিন্ন আকারে বড় এরর পেতাম। এখানে দেখানো জ্যামিতিক পদ্ধতিটা আরো ইনটুইটিভ এবং আরো সঠিক।

ইমপ্লিমেন্টেশন#

শুরুতে যেমন বলা হয়েছে, আমরা ধরে নিচ্ছি বৃত্তের কেন্দ্র মূলবিন্দুতে, এবং তাই প্রোগ্রামের ইনপুট হলো বৃত্তের ব্যাসার্ধ $r$ এবং রেখার ইকুয়েশনের প্যারামিটার $A$, $B$ ও $C$।

double r, a, b, c; // given as input
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
    puts ("no points");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
    puts ("1 point");
    cout << x0 << ' ' << y0 << '\n';
}
else {
    double d = r*r - c*c/(a*a+b*b);
    double mult = sqrt (d / (a*a+b*b));
    double ax, ay, bx, by;
    ax = x0 + b * mult;
    bx = x0 - b * mult;
    ay = y0 - a * mult;
    by = y0 + a * mult;
    puts ("2 points");
    cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}

অনুশীলন সমস্যা#

CODECHEF: ANDOOR