Problem link ও উৎস
- **Original source:** Classic exercise (school coordinate geometry-র distance formula)
- **Platform:** Classic exercise (related practice: nearest-point ধরনের problem সব judge-এ আছে)
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Easy
- **Pattern:** squared distance
- **Basic idea inherited from:** — (এটাই এই level-এর শিকড়; এখান থেকেই 119 আর 121 গজাবে)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো point দেওয়া আছে — `A = (x1, y1)` আর `B = (x2, y2)`। বলতে হবে এই দুটোর মধ্যে দূরত্ব কত।
দুটো রূপে উত্তর দরকার হতে পারে:
- **আসল দূরত্ব** (Euclidean distance) — যেটা স্কেলে মাপলে পাবে, যেমন 5.0
- **squared distance** — সেই দূরত্বের বর্গ, যেমন 25, কোনো ভগ্নাংশ ছাড়াই
আর একটা খুব সাধারণ প্রশ্ন: দুটো দূরত্বের মধ্যে **কোনটা বড়** — সেটা বলতে কিন্তু আসল দূরত্বই লাগে না, এটাই আজকের আসল মজা।
### Input ও output {#6-example-input-and-output}
```text
A B squared dist real dist
-------------------------------------------------
(0,0) (3,4) 25 5.0 (চেনা 3-4-5 triangle)
(1,1) (4,4) 18 4.2426...
(2,3) (2,3) 0 0.0 (একই point → দূরত্ব 0)
(-1,-1) (2,3) 25 5.0 (negative coordinate-ও চলে)
(0,0) (0,7) 49 7.0 (vertical — dx = 0, কোনো সমস্যা নেই)
```
খেয়াল করো: একই point দিলে দূরত্ব 0; negative coordinate দিলেও সূত্র একইভাবে কাজ করে (বিয়োগেই সব ঠিক হয়ে যায়); আর vertical/horizontal-এ কোনো special case লাগে না — distance formula-তে ভাগ নেই বলে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা শহরে তুমি সরলরেখায় (পাখির উড়ান, helicopter) এক বাড়ি থেকে আরেক বাড়ি যেতে চাও। পুবে কত হাঁটতে হবে (`dx`) আর উত্তরে কত (`dy`) — এই দুটো জানা থাকলে সরাসরি দূরত্ব Pythagoras বলে দেয়।
এবার ভাবো তুমি শুধু জানতে চাও — দুই বন্ধুর মধ্যে **কে আমার কাছে বেশি কাছে**। তখন আসল কিলোমিটার মেপে দশমিকে লেখার দরকার নেই; "বর্গ-দূরত্ব" তুলনা করলেই উত্তর পেয়ে যাবে, কারণ যে কাছে তার বর্গও ছোট। আসল মাপজোক (sqrt) তখনই দরকার যখন সংখ্যাটা **ছাপতে** হবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা Level 9-এর একদম প্রথম problem, তাই এর নিচে দাঁড়ানোর মতো আগের কোনো geometry problem নেই (তাই "inherited from: —")।
বরং উল্টোটা — এটাই সেই বীজ যেখান থেকে এই level-এর অনেক কিছু গজাবে:
- **119 (Circle and Point)** — point টা circle-এর ভেতরে কি না, পুরোটাই `dist2(point, center)` আর `r²`-এর তুলনা
- **121 (Manhattan Distance Tricks)** — যদিও সেখানে দূরত্বের সংজ্ঞা আলাদা, "দূরত্বকে সংখ্যা দিয়ে ধরা" চিন্তাটা এখান থেকেই
মানে আজ তুমি শুধু distance formula শিখছ না — তুমি "তুলনার জন্য sqrt লাগে না" এই সোনালি নিয়মটা শিখছ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea স্কুলের সেই চেনা সূত্র — **Pythagoras**। দুটো point-এর মধ্যে আনুভূমিক ফারাক `dx = x2 − x1`, আর উল্লম্ব ফারাক `dy = y2 − y1`। এই দুটো একটা সমকোণী triangle-এর দুই বাহু, আর দূরত্ব হলো অতিভুজ:
```
distance = √(dx² + dy²)
```
কিন্তু আসল programming-insight হলো: `√` মানেই float, আর float তুলনা মানেই বিপদ। সুখবর — **দূরত্ব তুলনা করতে sqrt লাগেই না**, কারণ দুটো অঋণাত্মক সংখ্যায় `a < b` হলে আর কেবল তখনই `a² < b²`। তাই তুলনার কাজে আমরা `dx² + dy²` (squared distance) integer-এ রেখে দিই — precision bug শূন্য।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
এখানে আসলে "brute force" বলতে যেটা প্রথমে মাথায় আসে — সরাসরি `math.sqrt` দিয়ে আসল দূরত্ব বের করে, সেটা দিয়েই সব তুলনা করা:
```python
import math
def dist(a, b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return math.sqrt(dx * dx + dy * dy)
# কে origin-এর কাছে?
p, q = (3, 4), (5, 1)
if dist(p, (0, 0)) < dist(q, (0, 0)):
print("p কাছে")
```
এটা ঠিক উত্তরই দেয়। কিন্তু প্রতিটা তুলনায় দুটো sqrt ডাকছি, আর float নিয়ে কাজ করছি — দুটোই অপ্রয়োজনীয় খরচ আর ঝুঁকি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
`sqrt` নিজে খুব ধীর না, কিন্তু সমস্যা দুটো:
```text
(1) প্রতিবার তুলনায় বাড়তি sqrt → অনেক point-এ অপ্রয়োজনীয় কাজ
(2) float তুলনা → 5.000000001 vs 5.0 এর মতো precision ফাঁদ
sqrt(25) -> 5.0 ভালোই দেখাচ্ছে...
কিন্তু কখনো sqrt(2)**2 != 2.0 হয়ে যায় (float-এ 1.9999999...)
```
বড় dataset-এ (যেমন "n point-এর মধ্যে সবচেয়ে কাছের জোড়া") এই বাড়তি sqrt আর float comparison দুটোই বাঁচানো যায় — শুধু squared-এ থেকে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation: **তুলনার সময় sqrt একটা monotonic (একমুখী) function — সে order বদলায় না।** মানে `√a < √b` ঠিক তখনই যখন `a < b` (a, b ≥ 0 হলে)। তাই দূরত্ব তুলনা করতে আসল দূরত্ব না নিয়ে squared distance তুলনা করলেই চলে:
```python
def dist2(a, b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return dx * dx + dy * dy # পুরোটা integer!
```
এখন সব তুলনা integer-এ, কোনো float নেই, কোনো sqrt নেই। আসল দূরত্ব দরকার হলে (শুধু ছাপার জন্য) তখনই একবার sqrt নিও।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **"কত দূর" আর "কে বেশি দূর" — এই দুটো আলাদা প্রশ্ন।**
- "কে বেশি দূর / কাছে" — squared distance-ই যথেষ্ট, integer-এ থাকো
- "ঠিক কত দূর (সংখ্যাটা ছাপব)" — তখনই, একদম শেষে, একবার sqrt
এই tweak-টা পুরো level-এর মন্ত্র। 119-এ circle-এর ভেতরে আছে কি না দেখতে আমরা ঠিক এই squared তুলনাই করব — `dist2 < r²`, কোথাও sqrt লাগবে না।
### ছবিতে বোঝা {#5-visual-explanation}
দূরত্ব আসলে একটা সমকোণী triangle-এর অতিভুজ — `dx` আর `dy` দুই বাহু:
```text
y
4 | B(4,4)
3 | /|
2 | / | dy = 4 - 1 = 3
1 | A(1,1)__/__|
0 | dx = 4 - 1 = 3
+------------------- x
0 1 2 3 4
dx = 3, dy = 3
squared distance = 3*3 + 3*3 = 18
real distance = sqrt(18) = 4.2426...
```
লক্ষ করো — squared distance 18 একটা পরিষ্কার integer, কোনো দশমিক নেই। আসল দূরত্ব `√18` হলো একটা irrational সংখ্যা, যেটা float-এ রাখলেই ছোটখাটো error ঢুকে পড়ে। তাই যতক্ষণ পারো, 18-এই থাকো।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `A = (1, 1)`, `B = (4, 4)` নিয়ে squared distance হাতে বের করি:
1. শুরুর অবস্থা: `A = (1, 1)`, `B = (4, 4)`
2. `dx = x2 − x1 = 4 − 1 = 3`
3. `dy = y2 − y1 = 4 − 1 = 3`
4. `dx*dx = 3*3 = 9`
5. `dy*dy = 3*3 = 9`
6. squared distance `= 9 + 9 = 18`
7. আসল দূরত্ব দরকার হলে: `√18 = 4.2426...`
দেখো, ধাপ 6 পর্যন্ত সব integer — পরিষ্কার, নিখুঁত। sqrt শুধু একদম শেষে, যদি আদৌ লাগে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import math
def dist2(a, b):
"""A আর B-র মধ্যে squared distance (integer থাকে, তুলনার জন্য আদর্শ)।"""
dx = a[0] - b[0]
dy = a[1] - b[1]
return dx * dx + dy * dy
def dist(a, b):
"""আসল Euclidean distance — শুধু সংখ্যাটা ছাপতে হলে এটা।"""
return math.sqrt(dist2(a, b))
def closer_to_origin(p, q):
"""origin-এর কাছে কোন point — sqrt ছাড়াই squared দিয়ে তুলনা।"""
o = (0, 0)
if dist2(p, o) < dist2(q, o):
return p
if dist2(q, o) < dist2(p, o):
return q
return None # সমান দূরত্ব
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert dist2((0, 0), (3, 4)) == 25 # 3-4-5 triangle
assert dist2((1, 1), (4, 4)) == 18
assert dist2((2, 3), (2, 3)) == 0 # একই point
assert dist2((-1, -1), (2, 3)) == 25 # negative coordinate
assert dist2((0, 0), (0, 7)) == 49 # vertical, special case লাগে না
assert dist((0, 0), (3, 4)) == 5.0 # sqrt(25) = 5.0
assert abs(dist((1, 1), (4, 4)) - 4.242640687) < 1e-9
assert closer_to_origin((3, 4), (5, 1)) == (3, 4) # 25 < 26
assert closer_to_origin((3, 4), (4, 3)) is None # 25 == 25, সমান
print(dist2((0, 0), (3, 4))) # 25
print(dist((0, 0), (3, 4))) # 5.0
print(closer_to_origin((3, 4), (5, 1))) # (3, 4)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def dist2(a, b):
dx = a[0] - b[0]
dy = a[1] - b[1]
return dx * dx + dy * dy
```
`a` আর `b` দুটো point (tuple)। `dx` হলো x-এর ফারাক, `dy` y-এর ফারাক। তারপর `dx*dx + dy*dy` — Pythagoras-এর ভেতরের অংশ, sqrt ছাড়া। পুরোটা integer থাকে, তাই তুলনায় নিখুঁত।
```
def dist(a, b):
return math.sqrt(dist2(a, b))
```
আসল দূরত্ব চাইলে squared-এর উপর একবার sqrt। লক্ষ করো — এটা `dist2`-কেই ডাকছে, মানে কোড repeat করিনি।
```
def closer_to_origin(p, q):
o = (0, 0)
if dist2(p, o) < dist2(q, o):
return p
...
```
`o` হলো origin। দুটো point-এর squared distance তুলনা করে কে কাছে বলছি — কোনো sqrt নেই। সমান হলে `None` (কেউ বেশি কাছে নয়)।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে — উত্তর মিললে চুপচাপ pass, না মিললে সেখানেই থেমে error। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
25
5.0
(3, 4)
সব test pass!
```
প্রথম লাইন `dist2((0,0),(3,4))` = 25 (squared, integer)। দ্বিতীয় লাইন আসল দূরত্ব 5.0। তৃতীয় লাইন — (3,4) origin-এর কাছে কারণ 25 < 26। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — দুটো point-এর জন্য কয়েকটা বিয়োগ-গুণ-যোগ, ব্যস। input-এর আকারের সাথে কাজ বাড়ে না।
(যদি "n point-এর মধ্যে সবচেয়ে কাছের জোড়া" খুঁজতে naive ভাবে সব জোড়া দেখো, সেটা O(n²) — কিন্তু সেখানেও প্রতিটা জোড়ার দূরত্ব হিসাব O(1)।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু গুটিকয় variable (`dx`, `dy`)। কোনো list বা array লাগছে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **তুলনার জন্যও sqrt নেওয়া** — শুধু "কে কাছে/দূর" জানতে squared-ই যথেষ্ট; sqrt মানেই float, আর float মানেই precision-এর দুঃস্বপ্ন।
2. **`dx` আর `dy`-তে absolute value নিতে ভুলে অস্থির হওয়া** — দরকার নেই! বর্গ করলে চিহ্ন এমনিতেই চলে যায় (`(-3)² = 9`)।
3. **vertical/horizontal-এ special case ভাবা** — distance formula-তে কোনো ভাগ নেই, তাই `dx = 0` বা `dy = 0` কোনো সমস্যাই না (slope-এর সাথে গুলিয়ে ফেলো না)।
4. **বড় coordinate-এ overflow ভয় (অন্য ভাষায়)** — Python-এ integer যত বড় খুশি, কিন্তু C++/Java-তে `dx*dx` overflow করতে পারে; সেখানে `long long` ভাবো।
5. **`==` দিয়ে float দূরত্ব তুলনা** — আসল দূরত্ব float-এ মিলিয়ে দেখলে `4.2426 == 4.2426` ভুল হতে পারে; squared (integer) দিয়ে মেলালে এই ঝামেলা নেই।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — K Closest Points to Origin** (