119 — Circle and Point¶

এই note-টা 113-এর সরাসরি জমজ ভাই। সেখানে squared distance শিখেছ যাতে sqrt না নিয়েও দূরত্ব তুলনা করা যায়। আজ সেই অস্ত্রটাই circle-এর গায়ে লাগাব: একটা point বৃত্তের ভেতরে, বাইরে, নাকি ঠিক ধারে — সেটা শুধু dist² আর r² তুলনা করেই বলে দেব। sqrt-এর ছায়াও পড়বে না, পুরোটা integer-এ নিখুঁত।

Source¶

Original source: Classic exercise (point-in-circle test, integer-only রূপে)
Platform: Classic exercise (circle containment সব geometry set-এ আছে)
Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
Difficulty: Easy
Pattern: r² compare
Basic idea inherited from: 113 — Distance Between Points (squared distance, এবার r²-এর সাথে তুলনা)

1. Problem in simple words¶

একটা বৃত্ত (circle) দেওয়া — তার কেন্দ্র C = (cx, cy) আর ব্যাসার্ধ r। সাথে একটা point P = (px, py)। বলতে হবে P কোথায়:

ভেতরে (inside) — point টা বৃত্তের সীমার ভেতরে
ঠিক ধারে (on the boundary) — point টা ঠিক পরিধির উপর
বাইরে (outside) — point টা বৃত্তের বাইরে

ব্যস — কেন্দ্র থেকে P-র দূরত্ব r-এর চেয়ে কম, সমান, নাকি বেশি — সেই তিনটে অবস্থা আলাদা করা।

2. What is the math idea?¶

মূল idea — একটা point বৃত্তের ভেতরে ⟺ কেন্দ্র থেকে তার দূরত্ব ব্যাসার্ধের চেয়ে কম। সাধারণভাবে:

dist(C, P) <  r   ->  ভেতরে
dist(C, P) == r   ->  ধারে
dist(C, P) >  r   ->  বাইরে

কিন্তু dist মানেই sqrt, আর sqrt মানেই float। তাই 113-এর মন্ত্র মেনে দুই পাশকেই বর্গ করি (দুটোই অঋণাত্মক, তাই অসমতা অটুট থাকে):

dist²(C, P) <  r²   ->  ভেতরে
dist²(C, P) == r²   ->  ধারে
dist²(C, P) >  r²   ->  বাইরে

যেখানে dist²(C, P) = (px − cx)² + (py − cy)² — পুরোটা integer (input integer হলে), আর r² integer। কোনো sqrt, কোনো float, কোনো precision-ফাঁদ।

3. Which basic idea does this inherit from?¶

113-এ আমরা শিখেছি দূরত্ব তুলনায় sqrt বাদ দিয়ে dx² + dy² integer-এ রাখা — কারণ a < b ⟺ a² < b² (অঋণাত্মকে)। এই problem ঠিক সেই নিয়মেরই সরাসরি প্রয়োগ।

"point বৃত্তের ভেতরে?" আসলে "দূরত্ব r-এর চেয়ে ছোট?" — একটা দূরত্ব তুলনা। আর দূরত্ব তুলনায় আমরা জানি squared-এ থাকতে হয়। তাই 119 আসলে 113-এর squared distance-কে একটা ধ্রুবক r²-এর সাথে মেলানো ছাড়া আর কিছুই নয়। দুটো problem এক সুতোয় গাঁথা — তাই এদের পাশাপাশি করার পরামর্শ।

4. Real-life analogy¶

ভাবো মাঠের মাঝখানে একটা স্প্রিংকলার (জল ছেটানোর যন্ত্র), যেটা r মিটার পর্যন্ত জল ছেটায়। তুমি দাঁড়িয়ে আছো P জায়গায় — ভিজবে কি না?

কেন্দ্র থেকে তোমার দূরত্ব r-এর কম → তুমি জলের নাগালে, ভিজবে (ভেতরে)
ঠিক r → একদম সীমানায়, ফোঁটা ছুঁই-ছুঁই (ধারে)
r-এর বেশি → শুকনো, বাইরে

আর চালাকি: তুমি ভিজবে কি না জানতে আসল দূরত্ব মেপে দশমিকে লেখার দরকার নেই — "দূরত্বের বর্গ" আর "r-এর বর্গ" তুলনা করলেই উত্তর। কারণ যে কাছে, তার বর্গও ছোট।

5. Visual explanation¶

কেন্দ্র থেকে দূরত্বের বর্গকে r²-এর সাথে তুলনা — তিনটে অঞ্চল:

        y
      4 |        . . .
      3 |      .   X   .       circle: center C(2,2), r = 2  ->  r² = 4
      2 |     . C(2,2) .       X = P(2,3): dist² = 0+1 = 1 < 4 -> ভেতরে
      1 |      .  Y  .         Y = P(2,1): dist² = 0+1 = 1 < 4 -> ভেতরে
      0 |        . . .         Z = P(5,2): dist² = 9+0 = 9 > 4 -> বাইরে
        +---------------- x    W = P(4,2): dist² = 4+0 = 4 == 4 -> ধারে
           0 1 2 3 4 5

dist² < r²  ->  ভেতরে
dist² == r² ->  ধারে (পরিধির উপর)
dist² > r²  ->  বাইরে

লক্ষ করো — সব দূরত্ব বর্গে রেখেছি (1, 9, 4), কোনো sqrt নেই। W point-এ dist² ঠিক r²-এর সমান (4 == 4), তাই সে একদম ধারে।

6. Example input and output¶

center   r    point     dist²        r²    অবস্থান
-------------------------------------------------------
(0,0)    5    (3,4)     9+16=25      25    ধারে   (চেনা 3-4-5)
(0,0)    5    (1,1)     1+1=2        25    ভেতরে
(0,0)    5    (5,5)     25+25=50     25    বাইরে
(2,2)    2    (2,2)     0            4     ভেতরে  (কেন্দ্রই, দূরত্ব 0)
(2,2)    2    (4,2)     4+0=4        4     ধারে
(-1,-1)  3    (1,1)     4+4=8        9     ভেতরে  (negative center)

খেয়াল করো: (3,4) point-টা r=5 বৃত্তের ঠিক ধারে (25 == 25) — চেনা 3-4-5 triangle; কেন্দ্রের দূরত্ব 0 মানে অবশ্যই ভেতরে; আর negative center দিলেও বিয়োগেই সব ঠিক হয়ে যায়।

7. Brute force thinking¶

প্রথমে যা মাথায় আসে — সরাসরি sqrt দিয়ে আসল দূরত্ব বের করে r-এর সাথে তুলনা:

import math

def location_bad(cx, cy, r, px, py):
    d = math.sqrt((px - cx)**2 + (py - cy)**2)   # sqrt -> float
    if d < r:
        return "inside"
    if d == r:                                    # float == -> বিপজ্জনক!
        return "on"
    return "outside"

এটা মোটামুটি কাজ করে, কিন্তু d == r float তুলনা — sqrt(25) যদি ঠিক 5.0 না হয়ে 4.9999999... আসে, তাহলে "on" ধরা পড়বে না। sqrt আর float == দুটোই precision-ফাঁদ।

8. Why brute force may be slow¶

"slow" নয় ঠিক, বরং float-ভঙ্গুর — বিশেষ করে "ঠিক ধারে" ধরতে গিয়ে:

sqrt পথ:  d = sqrt(dist²) -> float
          "ধারে" চেক: d == r -> 4.9999999... == 5.0 -> False (ভুল!)
          inside/outside-এ একটু কম বিপজ্জনক, কিন্তু "ধারে" প্রায়ই হাতছাড়া

r² পথ:    dist² == r² -> 25 == 25 -> True (integer, নিখুঁত)
          কোনো epsilon, কোনো sqrt, কোনো ভুল boundary

মূল কথা — boundary case ("ঠিক ধারে") integer তুলনায় নিখুঁত, কিন্তু sqrt + float ==-এ প্রায় ধরাই পড়ে না। তাই squared-এ থাকা শুধু দ্রুততা নয়, শুদ্ধতার জন্য জরুরি।

9. Better thinking¶

মূল insight: "r-এর চেয়ে কাছে/দূরে" = squared distance বনাম r² — sqrt লাগে না। তাই:

def location(cx, cy, r, px, py):
    d2 = (px - cx)**2 + (py - cy)**2     # squared distance, integer
    r2 = r * r
    if d2 < r2:
        return "inside"
    if d2 == r2:
        return "on"
    return "outside"

সব integer (input integer হলে): d2, r2, আর তুলনা। d2 == r2 boundary নিখুঁতভাবে ধরে — কোনো float নেই। এটাই 113-এর squared distance-এর সরাসরি ফসল।

10. Thinking tweak¶

আসল "আহা!": বৃত্তের সংজ্ঞাটাই (dist == r) দুই পাশে বর্গ করে integer-এ নামিয়ে আনো — dist² == r² — তখন inside/on/outside তিনটেই নিখুঁত, sqrt ছাড়া।

এটা 113-এর "তুলনায় sqrt লাগে না" মন্ত্রের নিখুঁত পুনরাবৃত্তি, শুধু এবার তুলনার অন্য পাশে একটা ধ্রুবক r²। মনে রাখো — যখনই "দূরত্ব বনাম একটা threshold" দেখবে (বৃত্ত, range, nearest-within-radius), দুই পাশ বর্গ করে integer-এ নেমে এসো। এই অভ্যাস precision-bug-এর দরজাই বন্ধ করে দেয়।

11. Step-by-step dry run¶

চলো center (0,0), r = 5, point (3,4) — কোথায়?

শুরু: cx=0, cy=0, r=5, px=3, py=4
px − cx = 3 − 0 = 3
py − cy = 4 − 0 = 4
d2 = 3² + 4² = 9 + 16 = 25
r2 = 5 × 5 = 25
d2 < r2? 25 < 25? না
d2 == r2? 25 == 25? হ্যাঁ → "on" (ঠিক ধারে) ✓

এবার একই বৃত্তে (1,1):

d2 = 1² + 1² = 2
r2 = 25
2 < 25 ✓  ->  "inside"

প্রতিটা ধাপ integer; d2 == r2-তে boundary নিখুঁতভাবে ধরা পড়ল — কোনো float-আন্দাজ ছাড়াই।

12. Python solution¶

def dist2(cx, cy, px, py):
    """center আর point-এর squared distance (113-এর মতো, integer)।"""
    dx = px - cx
    dy = py - cy
    return dx * dx + dy * dy


def location(cx, cy, r, px, py):
    """point বৃত্তের কোথায়: 'inside' / 'on' / 'outside' — sqrt ছাড়াই।"""
    d2 = dist2(cx, cy, px, py)
    r2 = r * r
    if d2 < r2:
        return "inside"
    if d2 == r2:
        return "on"
    return "outside"


def inside_or_on(cx, cy, r, px, py):
    """ভেতরে বা ধারে হলে True (অনেক problem-এ এটাই দরকার)।"""
    return dist2(cx, cy, px, py) <= r * r


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert location(0, 0, 5, 3, 4) == "on"        # 25 == 25 (3-4-5)
assert location(0, 0, 5, 1, 1) == "inside"    # 2 < 25
assert location(0, 0, 5, 5, 5) == "outside"   # 50 > 25
assert location(2, 2, 2, 2, 2) == "inside"    # কেন্দ্রই, dist 0
assert location(2, 2, 2, 4, 2) == "on"        # 4 == 4
assert location(-1, -1, 3, 1, 1) == "inside"  # negative center, 8 < 9

assert inside_or_on(0, 0, 5, 3, 4) is True    # ধারেও True
assert inside_or_on(0, 0, 5, 5, 5) is False   # বাইরে -> False
assert inside_or_on(0, 0, 5, 0, 0) is True    # কেন্দ্র -> True

print(location(0, 0, 5, 3, 4))    # on
print(location(0, 0, 5, 1, 1))    # inside
print(location(0, 0, 5, 5, 5))    # outside
print("সব test pass!")

13. Line-by-line explanation¶

def dist2(cx, cy, px, py):
    dx = px - cx
    dy = py - cy
    return dx * dx + dy * dy

113-এর সেই squared distance — কেন্দ্র থেকে point-এর x আর y ফারাকের বর্গের যোগ। পুরোটা integer, sqrt নেই।

def location(cx, cy, r, px, py):
    d2 = dist2(cx, cy, px, py)
    r2 = r * r
    if d2 < r2:
        return "inside"
    if d2 == r2:
        return "on"
    return "outside"

d2 হলো squared distance, r2 = r²। দুটোই integer। d2 < r2 ভেতরে, সমান হলে ধারে, বেশি হলে বাইরে। d2 == r2-এ boundary নিখুঁত — কোনো float == ঝুঁকি নেই।

def inside_or_on(cx, cy, r, px, py):
    return dist2(cx, cy, px, py) <= r * r

অনেক problem-এ শুধু "ভেতরে বা ধারে কি না" দরকার — এক লাইনে <= r²। (ধার বাদ দিতে চাইলে <।)

বাকি assert লাইনগুলো — ধারে, ভেতরে, বাইরে, কেন্দ্র, negative center — সব যাচাই করছে; সব মিললে শেষে সব test pass!।

14. Output walkthrough¶

চালালে যা ছাপবে:

on
inside
outside
সব test pass!

প্রথম: (3,4) r=5 বৃত্তের ঠিক ধারে (25 == 25) → on। দ্বিতীয়: (1,1) ভেতরে (2 < 25) → inside। তৃতীয়: (5,5) বাইরে (50 > 25) → outside। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity¶

O(1) — একটা squared distance (কয়েকটা বিয়োগ-গুণ-যোগ) আর দুটো তুলনা। input-নির্বিশেষে ধ্রুবক।

(n point-এর মধ্যে কতগুলো বৃত্তে আছে গুনতে হলে O(n) — প্রতিটার চেক O(1)।)

16. Space complexity¶

O(1) — শুধু d2, r2, dx, dy — গুটিকয় variable। কোনো বাড়তি জায়গা নেই।

17. Common mistakes¶

boundary-তে sqrt + float == ব্যবহার — sqrt(25) == 5.0 সবসময় সত্যি না হতে পারে; integer d2 == r² নিখুঁত।
r² বের করতে ভুলে r দিয়ে তুলনা — d2 < r লিখলে সম্পূর্ণ ভুল মাত্রা; দুই পাশ একই (squared) রাখো — d2 < r²।
< আর <= গুলিয়ে ফেলা — ধার (on) ভেতরে ধরবে কি না, সংজ্ঞা দেখে ঠিক করো (inside_or_on-এ <=)।
negative center/point ভয় পাওয়া — বিয়োগ আর বর্গে চিহ্ন এমনিতেই চলে যায়, কোনো special handling লাগে না।
বড় coordinate-এ overflow (অন্য ভাষায়) — dx*dx + dy*dy আর r*r C++/Java-তে overflow করতে পারে; long long/long ভাবো (Python-এ এ সমস্যা নেই)।

18. Harder problems that inherit this idea¶

LeetCode — Queries on Number of Points Inside a Circle (https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle/) — প্রতিটা query বৃত্তে কতগুলো point — ঠিক এই dist² <= r² গোনা।
LeetCode — Circle and Rectangle Overlapping (https://leetcode.com/problems/circle-and-rectangle-overlapping/) — circle আর rectangle-এর মিল; নিকটতম point খুঁজে squared distance তুলনা।
113 (Distance Between Points) — এই problem-এর শিকড়; squared distance-এর জন্মস্থান।

19. Pattern learned¶

Point-in-circle via r² compare — dist²(C, P)-কে r²-এর সাথে তুলনা করে inside/on/outside; sqrt লাগে না, boundary নিখুঁত। বড় শিক্ষা: "দূরত্ব বনাম একটা threshold" দেখলেই দুই পাশ বর্গ করে integer-এ নেমে এসো — তুলনা শুদ্ধ থাকে, float-bug মরে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "point বৃত্তে আছে কি না = dist² vs r²; < ভেতরে, == ধারে, > বাইরে — sqrt ছাড়া, boundary নিখুঁত। 113-এর squared distance এখানে শুধু r²-এর সাথে মেলে। threshold দেখলেই বর্গ করো।"

পরের ধাপ → 120 — Convex Hull Intro (এবার Hard — rubber band-এর গণিত)। শিকড় → 113 — Distance Between Points।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।