Problem link ও উৎস
- **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²-এর সাথে তুলনা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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-এর চেয়ে কম, সমান, নাকি বেশি — সেই তিনটে অবস্থা আলাদা করা।
### Input ও output {#6-example-input-and-output}
```text
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 দিলেও বিয়োগেই সব ঠিক হয়ে যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো মাঠের মাঝখানে একটা স্প্রিংকলার (জল ছেটানোর যন্ত্র), যেটা `r` মিটার পর্যন্ত জল ছেটায়। তুমি দাঁড়িয়ে আছো P জায়গায় — ভিজবে কি না?
- কেন্দ্র থেকে তোমার দূরত্ব r-এর কম → তুমি জলের নাগালে, ভিজবে (ভেতরে)
- ঠিক r → একদম সীমানায়, ফোঁটা ছুঁই-ছুঁই (ধারে)
- r-এর বেশি → শুকনো, বাইরে
আর চালাকি: তুমি ভিজবে কি না জানতে আসল দূরত্ব মেপে দশমিকে লেখার দরকার নেই — "দূরত্বের বর্গ" আর "r-এর বর্গ" তুলনা করলেই উত্তর। কারণ যে কাছে, তার বর্গও ছোট।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 এক সুতোয় গাঁথা — তাই এদের পাশাপাশি করার পরামর্শ।
### ভেতরের অঙ্ক {#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-ফাঁদ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যা মাথায় আসে — সরাসরি sqrt দিয়ে আসল দূরত্ব বের করে r-এর সাথে তুলনা:
```python
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-ভঙ্গুর** — বিশেষ করে "ঠিক ধারে" ধরতে গিয়ে:
```text
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 লাগে না।** তাই:
```python
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-এর দরজাই বন্ধ করে দেয়।
### ছবিতে বোঝা {#5-visual-explanation}
কেন্দ্র থেকে দূরত্বের বর্গকে r²-এর সাথে তুলনা — তিনটে অঞ্চল:
```text
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), তাই সে একদম ধারে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো center `(0,0)`, `r = 5`, point `(3,4)` — কোথায়?
1. শুরু: cx=0, cy=0, r=5, px=3, py=4
2. `px − cx = 3 − 0 = 3`
3. `py − cy = 4 − 0 = 4`
4. `d2 = 3² + 4² = 9 + 16 = 25`
5. `r2 = 5 × 5 = 25`
6. `d2 < r2`? `25 < 25`? না
7. `d2 == r2`? `25 == 25`? হ্যাঁ → **"on"** (ঠিক ধারে) ✓
এবার একই বৃত্তে `(1,1)`:
```text
d2 = 1² + 1² = 2
r2 = 25
2 < 25 ✓ -> "inside"
```
প্রতিটা ধাপ integer; `d2 == r2`-তে boundary নিখুঁতভাবে ধরা পড়ল — কোনো float-আন্দাজ ছাড়াই।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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!`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **boundary-তে sqrt + float == ব্যবহার** — `sqrt(25) == 5.0` সবসময় সত্যি না হতে পারে; integer `d2 == r²` নিখুঁত।
2. **`r²` বের করতে ভুলে `r` দিয়ে তুলনা** — `d2 < r` লিখলে সম্পূর্ণ ভুল মাত্রা; দুই পাশ একই (squared) রাখো — `d2 < r²`।
3. **`<` আর `<=` গুলিয়ে ফেলা** — ধার (on) ভেতরে ধরবে কি না, সংজ্ঞা দেখে ঠিক করো (`inside_or_on`-এ `<=`)।
4. **negative center/point ভয় পাওয়া** — বিয়োগ আর বর্গে চিহ্ন এমনিতেই চলে যায়, কোনো special handling লাগে না।
5. **বড় coordinate-এ overflow (অন্য ভাষায়)** — `dx*dx + dy*dy` আর `r*r` C++/Java-তে overflow করতে পারে; `long long`/`long` ভাবো (Python-এ এ সমস্যা নেই)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Queries on Number of Points Inside a Circle** (