113 — Distance Between Points¶

এই note দিয়েই Level 9-এর যাত্রা শুরু — অভিনন্দন! Geometry শুনে ভয় পেও না, প্রথম problem-টা একদম মাটির কাছাকাছি: দুটো point-এর মধ্যে দূরত্ব। কিন্তু এখানেই তুমি শিখবে এই level-এর সবচেয়ে দরকারি অভ্যাস — sqrt না নিয়ে squared distance-এ থাকা। এই একটা idea তোমাকে অসংখ্য floating point bug থেকে বাঁচাবে।

Source¶

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 গজাবে)

1. Problem in simple words¶

দুটো point দেওয়া আছে — A = (x1, y1) আর B = (x2, y2)। বলতে হবে এই দুটোর মধ্যে দূরত্ব কত।

দুটো রূপে উত্তর দরকার হতে পারে:

আসল দূরত্ব (Euclidean distance) — যেটা স্কেলে মাপলে পাবে, যেমন 5.0
squared distance — সেই দূরত্বের বর্গ, যেমন 25, কোনো ভগ্নাংশ ছাড়াই

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

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 শূন্য।

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 লাগে না" এই সোনালি নিয়মটা শিখছ।

4. Real-life analogy¶

ভাবো একটা শহরে তুমি সরলরেখায় (পাখির উড়ান, helicopter) এক বাড়ি থেকে আরেক বাড়ি যেতে চাও। পুবে কত হাঁটতে হবে (dx) আর উত্তরে কত (dy) — এই দুটো জানা থাকলে সরাসরি দূরত্ব Pythagoras বলে দেয়।

এবার ভাবো তুমি শুধু জানতে চাও — দুই বন্ধুর মধ্যে কে আমার কাছে বেশি কাছে। তখন আসল কিলোমিটার মেপে দশমিকে লেখার দরকার নেই; "বর্গ-দূরত্ব" তুলনা করলেই উত্তর পেয়ে যাবে, কারণ যে কাছে তার বর্গও ছোট। আসল মাপজোক (sqrt) তখনই দরকার যখন সংখ্যাটা ছাপতে হবে।

5. Visual explanation¶

দূরত্ব আসলে একটা সমকোণী triangle-এর অতিভুজ — dx আর dy দুই বাহু:

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-এই থাকো।

6. Example input and output¶

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-তে ভাগ নেই বলে।

7. Brute force thinking¶

এখানে আসলে "brute force" বলতে যেটা প্রথমে মাথায় আসে — সরাসরি math.sqrt দিয়ে আসল দূরত্ব বের করে, সেটা দিয়েই সব তুলনা করা:

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 নিজে খুব ধীর না, কিন্তু সমস্যা দুটো:

(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 তুলনা করলেই চলে:

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 লাগবে না।

11. Step-by-step dry run¶

চলো A = (1, 1), B = (4, 4) নিয়ে squared distance হাতে বের করি:

শুরুর অবস্থা: A = (1, 1), B = (4, 4)
dx = x2 − x1 = 4 − 1 = 3
dy = y2 − y1 = 4 − 1 = 3
dx*dx = 3*3 = 9
dy*dy = 3*3 = 9
squared distance = 9 + 9 = 18
আসল দূরত্ব দরকার হলে: √18 = 4.2426...

দেখো, ধাপ 6 পর্যন্ত সব integer — পরিষ্কার, নিখুঁত। sqrt শুধু একদম শেষে, যদি আদৌ লাগে।

12. Python solution¶

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! ছাপে।

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!।

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¶

তুলনার জন্যও sqrt নেওয়া — শুধু "কে কাছে/দূর" জানতে squared-ই যথেষ্ট; sqrt মানেই float, আর float মানেই precision-এর দুঃস্বপ্ন।
dx আর dy-তে absolute value নিতে ভুলে অস্থির হওয়া — দরকার নেই! বর্গ করলে চিহ্ন এমনিতেই চলে যায় ((-3)² = 9)।
vertical/horizontal-এ special case ভাবা — distance formula-তে কোনো ভাগ নেই, তাই dx = 0 বা dy = 0 কোনো সমস্যাই না (slope-এর সাথে গুলিয়ে ফেলো না)।
বড় coordinate-এ overflow ভয় (অন্য ভাষায়) — Python-এ integer যত বড় খুশি, কিন্তু C++/Java-তে dx*dx overflow করতে পারে; সেখানে long long ভাবো।
== দিয়ে float দূরত্ব তুলনা — আসল দূরত্ব float-এ মিলিয়ে দেখলে 4.2426 == 4.2426 ভুল হতে পারে; squared (integer) দিয়ে মেলালে এই ঝামেলা নেই।

18. Harder problems that inherit this idea¶

LeetCode — K Closest Points to Origin (https://leetcode.com/problems/k-closest-points-to-origin/) — ঠিক এই squared distance দিয়ে sort/heap; sqrt লাগেই না।
CSES — Maximum Manhattan Distances (https://cses.fi/problemset/task/2185) — দূরত্বের ধারণা, কিন্তু Manhattan রূপে (problem 121-এ আসছে)।
119 (Circle and Point) — এই repo-রই পরের ধাপ, যেখানে squared distance সরাসরি r²-এর সাথে তুলনা হবে।

19. Pattern learned¶

Squared distance for comparison — দুটো দূরত্ব তুলনা করতে dx² + dy² integer-এ রাখো, sqrt শুধু একদম শেষে ছাপার জন্য। বড় শিক্ষা: monotonic function (যেমন sqrt) order বদলায় না, তাই তুলনার আগে সেটা প্রয়োগ করা স্রেফ অপচয় আর precision-ঝুঁকি।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "দূরত্ব = √(dx²+dy²); কিন্তু তুলনা করতে sqrt লাগে না — dx²+dy² integer-এ রাখো, sqrt শুধু ছাপার সময়। এই 'squared-এ থাকো' অভ্যাসটাই গোটা geometry level-এ float-bug থেকে বাঁচাবে।"

পরের ধাপ → 114 — Slope and Collinearity (এবার ভাগের ফাঁদ এড়িয়ে cross multiplication)। সম্পর্কিত → 119 — Circle and Point।

ফিরে দেখা: এই 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" লেখো।