Skip to content

114 — Slope and Collinearity

এই note-এ আমরা একটা ছোট কিন্তু ভয়ংকর ফাঁদের মুখোমুখি হব — ভাগ। স্কুলে slope শিখেছ (y2−y1)/(x2−x1) দিয়ে, কিন্তু programming-এ এই ভাগটাই দুটো বিপদ ডেকে আনে: vertical line-এ শূন্য দিয়ে ভাগ, আর float-এ 1/3 ≠ 0.333...। আজ শিখব কীভাবে ভাগকে গুণে বদলে (cross multiplication) দুটো বিপদই এক ঝটকায় উড়িয়ে দেওয়া যায়।

Source

  • Original source: Classic exercise (school slope + collinearity, integer-only রূপে)
  • Platform: Classic exercise (collinearity check প্রায় সব geometry set-এ আছে)
  • Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
  • Difficulty: Easy
  • Pattern: cross multiply
  • Basic idea inherited from: 113 — Distance Between Points (একই "ভাগ/float এড়াও, integer-এ থাকো" দর্শন)

1. Problem in simple words

দুই ভাগে প্রশ্ন:

  • Slope: দুটো point A আর B দেওয়া; এদের দিয়ে যাওয়া সরলরেখার ঢাল (slope) কত — মানে x একক ডানে গেলে y কত ওঠে/নামে।
  • Collinearity: তিনটা point A, B, C দেওয়া; এরা কি একই সরলরেখায় (collinear) আছে নাকি নেই?

আসল চ্যালেঞ্জ slope-এর সংখ্যাটা বের করা নয় — চ্যালেঞ্জ হলো ভাগ না করে, error ছাড়া, float ছাড়া এই প্রশ্নগুলোর উত্তর দেওয়া।

2. What is the math idea?

স্কুলের সূত্র: A থেকে B-র slope = (y2 − y1) / (x2 − x1)। তিনটা point collinear হলে AB-র slope আর AC-র slope সমান:

(y2 − y1) / (x2 − x1) == (y3 − y1) / (x3 − x1)

কিন্তু ভাগ মানেই বিপদ। মূল programming-idea: ভাগকে গুণে বদলাও (cross multiplication)। দুই পাশে cross গুণ করলে:

(y2 − y1) * (x3 − x1) == (y3 − y1) * (x2 − x1)

এখন কোনো ভাগ নেই, তাই শূন্য দিয়ে ভাগের ভয় নেই; সব integer, তাই float-এর মিল-অমিলের ঝামেলা নেই। (একটু আগে দৌড়ে গিয়ে বলি — এই গুণফলের পার্থক্যটাই আসলে cross product, যেটা 116-এ orientation হয়ে ফিরবে।)

3. Which basic idea does this inherit from?

113-এ আমরা শিখেছি দূরত্ব তুলনায় sqrt বাদ দিয়ে integer-এ থাকার মূল্য। এই problem সেই একই দর্শনের আরেকটা রূপ — কিন্তু এবার শত্রু sqrt নয়, ভাগ।

113-এর শিক্ষা ছিল: "float এড়াও, যতক্ষণ পারো integer-এ থাকো।" এখানে সেটাই প্রয়োগ করছি slope-এ — ভাগ (যা float আর ZeroDivisionError আনে) সরিয়ে গুণে নামিয়ে আনছি। মানে দুটো problem একই বড় নিয়মের দুই উদাহরণ: precision-নিরাপদ থাকতে চাইলে float-জন্মদানকারী operation (sqrt, ভাগ) যথাসম্ভব দেরিতে, বা একেবারেই নয়।

4. Real-life analogy

ভাবো একটা পাহাড়ি রাস্তার ঢাল মাপছ — "প্রতি 4 মিটার সামনে গেলে 2 মিটার ওঠে।" তুমি বলতে পারো ঢাল 2/4 = 0.5। কিন্তু একটা জায়গায় রাস্তা একদম খাড়া দেয়াল — সামনে 0 মিটার, উপরে 5 মিটার। তখন 5/0? অর্থহীন! ঢাল "অসীম"।

Collinearity-তে আমরা চালাকি করি: দুটো ঢাল মেলানোর বদলে জিজ্ঞেস করি "প্রথম রাস্তার (সামনে, উপরে) আর দ্বিতীয়টার (সামনে, উপরে) কি একই অনুপাতে?" — সেটা ভাগ ছাড়াই cross গুণে মেলানো যায়। খাড়া দেয়াল (vertical) হোক বা না হোক, গুণে কোনো অসুবিধা নেই।

5. Visual explanation

তিনটা point একই লাইনে থাকলে A→B তীর আর A→C তীর একই দিকে নির্দেশ করে — অনুপাত মেলে:

collinear (এক লাইনে):            not collinear (বাঁকা):
y                                 y
3 |        C(3,3)                 3 |        C(3,3)
2 |     B(2,2)                    2 |
1 |  A(1,1)                       1 |  A(1,1)  B(2,1)
  +-------------- x                 +-------------- x
     1  2  3                           1  2  3

AB=(1,1), AC=(2,2)                AB=(1,0), AC=(2,2)
(1)*(2) == (1)*(2)? 2==2 ✓        (1)*(2) == (0)*(2)? 2==0 ✗
   -> collinear                      -> NOT collinear

লক্ষ করো — বাঁ দিকে গুণফল দুই পাশে সমান (2 == 2), তাই এক লাইনে। ডান দিকে অসমান (2 ≠ 0), তাই বাঁকা। কোথাও ভাগ করিনি।

6. Example input and output

collinearity (তিন point):
A(0,0) B(1,1) C(2,2)   -> True   (y = x লাইন)
A(0,0) B(0,5) C(0,9)   -> True   (vertical line! ভাগ হলে crash হতো)
A(0,0) B(1,1) C(2,3)   -> False
A(1,1) B(1,1) C(5,5)   -> True   (দুটো point একই — degenerate, এক লাইনে ধরা)

slope (দুই point, ভাগ করে কেবল ছাপার জন্য):
A(1,1) B(4,3)  -> slope = 2/3 ≈ 0.6667
A(0,0) B(0,5)  -> slope = undefined (vertical, dx = 0)
A(0,0) B(5,0)  -> slope = 0 (horizontal)

দুটো জিনিস খেয়াল করো: vertical line (dx = 0) collinearity check-এ দিব্যি কাজ করে কারণ ভাগ নেই; আর slope-এর আসল সংখ্যা চাইলে vertical-এ "undefined" আলাদা করে handle করতে হয়।

7. Brute force thinking

প্রথমে যা মাথায় আসে — স্কুলের সূত্র সরাসরি, ভাগ করে slope মিলিয়ে:

def collinear_bad(a, b, c):
    slope_ab = (b[1] - a[1]) / (b[0] - a[0])   # dx == 0 হলে crash!
    slope_ac = (c[1] - a[1]) / (c[0] - a[0])
    return slope_ab == slope_ac

এটা সাধারণ case-এ উত্তর দেয়, কিন্তু দুটো গোপন বোমা: (1) b[0] == a[0] হলে ZeroDivisionError; (2) দুটো float slope == দিয়ে মেলানো — 1/3 আর অন্য পথে পাওয়া 0.333... নাও মিলতে পারে।

8. Why brute force may be slow

এখানে "slow" নয়, বরং ভুল আর ভঙ্গুর — যেটা আরও বিপজ্জনক:

সমস্যা 1: vertical line
  A(0,0) B(0,5):  (5-0)/(0-0) = 5/0  -> ZeroDivisionError, program ক্র্যাশ

সমস্যা 2: float তুলনা
  slope একপথে 0.1+0.2 = 0.30000000000000004
  অন্যপথে        0.3
  0.30000000000000004 == 0.3  ->  False  (অথচ collinear!)  -> ভুল উত্তর

মানে brute force শুধু কিছু input-এ crash করে, আর কিছু input-এ চুপচাপ ভুল উত্তর দেয় — দুটোই interview-তে মৃত্যু।

9. Better thinking

মূল insight: slope-এর সংখ্যাটা আসলে দরকার নেই — শুধু "অনুপাত সমান কি না" জানলেই চলে। আর অনুপাত সমান কি না, সেটা cross গুণে ভাগ ছাড়াই বলা যায়:

def collinear(a, b, c):
    return (b[1] - a[1]) * (c[0] - a[0]) == (c[1] - a[1]) * (b[0] - a[0])

কোনো ভাগ নেই → শূন্য দিয়ে ভাগের ভয় নেই। সব integer → float-এর মিল-অমিলের ঝামেলা নেই। vertical, horizontal, degenerate — সব case একই লাইনে handle হয়ে যায়।

10. Thinking tweak

আসল "আহা!": a/b == c/d প্রশ্নটা a*d == c*b প্রশ্নের সমান (যতক্ষণ ভাগের চিহ্ন নিয়ে সাবধান) — তাই ভাগটা পুরো বাদ দিয়ে গুণে নেমে এসো।

এই ছোট মোচড় slope-এর সব দুর্বলতা একসাথে সারিয়ে দেয়। আর সবচেয়ে দারুণ — এই (b−a) × (c−a) রাশিটাই হলো cross product, যেটা 116-এ শুধু "সমান কি না" নয়, "কোন দিকে বাঁকা" (orientation) পর্যন্ত বলে দেবে। মানে আজকের collinearity test আসলে cross product-এর প্রথম পরিচয়।

11. Step-by-step dry run

চলো A=(0,0), B=(1,1), C=(2,3) — এরা collinear কি না হাতে দেখি:

  1. শুরুর অবস্থা: A=(0,0), B=(1,1), C=(2,3)
  2. বাঁ পাশ: (B.y − A.y) * (C.x − A.x) = (1 − 0) * (2 − 0) = 1 * 2 = 2
  3. ডান পাশ: (C.y − A.y) * (B.x − A.x) = (3 − 0) * (1 − 0) = 3 * 1 = 3
  4. তুলনা: 2 == 3? না।
  5. শেষ অবস্থা: সমান নয় → NOT collinear (C লাইনের বাইরে, একটু উপরে)

এবার vertical case A=(0,0), B=(0,5), C=(0,9) — যেখানে ভাগ crash করত:

বাঁ পাশ: (5-0)*(0-0) = 5*0 = 0
ডান পাশ: (9-0)*(0-0) = 9*0 = 0
0 == 0 ✓  -> collinear, কোনো crash ছাড়াই

12. Python solution

def collinear(a, b, c):
    """A, B, C এক লাইনে কি না — cross multiplication, কোনো ভাগ/float নেই।"""
    return (b[1] - a[1]) * (c[0] - a[0]) == (c[1] - a[1]) * (b[0] - a[0])


def slope_fraction(a, b):
    """slope-কে সর্বনিম্ন রূপের ভগ্নাংশ (dy, dx) হিসেবে ফেরায় — ভাগ ছাড়াই।
    vertical হলে dx = 0; এটা integer-এ slope তুলনার নিরাপদ উপায়।"""
    from math import gcd
    dy = b[1] - a[1]
    dx = b[0] - a[0]
    g = gcd(abs(dy), abs(dx))
    if g == 0:
        return (0, 0)          # দুটো point একই
    dy, dx = dy // g, dx // g
    if dx < 0 or (dx == 0 and dy < 0):   # চিহ্ন একরকম রাখি
        dy, dx = -dy, -dx
    return (dy, dx)


def slope_value(a, b):
    """আসল slope সংখ্যা — শুধু ছাপার জন্য; vertical হলে None।"""
    dx = b[0] - a[0]
    if dx == 0:
        return None            # vertical: slope undefined
    return (b[1] - a[1]) / dx


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert collinear((0, 0), (1, 1), (2, 2)) is True       # y = x
assert collinear((0, 0), (0, 5), (0, 9)) is True       # vertical, crash নেই
assert collinear((0, 0), (1, 1), (2, 3)) is False
assert collinear((1, 1), (1, 1), (5, 5)) is True       # degenerate (দুটো একই)

assert slope_fraction((1, 1), (4, 3)) == (2, 3)        # 2/3
assert slope_fraction((0, 0), (0, 5)) == (1, 0)        # vertical -> dx = 0
assert slope_fraction((0, 0), (5, 0)) == (0, 1)        # horizontal -> 0
assert slope_fraction((0, 0), (2, 4)) == (2, 1)        # 4/2 = 2

assert slope_value((1, 1), (4, 3)) == 2 / 3
assert slope_value((0, 0), (0, 5)) is None             # vertical -> None
assert slope_value((0, 0), (5, 0)) == 0.0

print(collinear((0, 0), (1, 1), (2, 2)))   # True
print(collinear((0, 0), (1, 1), (2, 3)))   # False
print(slope_fraction((1, 1), (4, 3)))      # (2, 3)
print("সব test pass!")

13. Line-by-line explanation

def collinear(a, b, c):
    return (b[1] - a[1]) * (c[0] - a[0]) == (c[1] - a[1]) * (b[0] - a[0])

এটাই হৃদয়। (b.y−a.y) হলো AB-র উল্লম্ব ফারাক, (c.x−a.x) হলো AC-র আনুভূমিক ফারাক — এদের গুণ। ডান পাশে উল্টোটা। দুটো সমান হলে slope সমান, মানে এক লাইনে — সব integer, কোনো ভাগ নেই।

def slope_fraction(a, b):
    ...
    g = gcd(abs(dy), abs(dx))
    ...
    dy, dx = dy // g, dx // g

slope-কে নিরাপদে তুলনাযোগ্য রাখতে আমরা একে সর্বনিম্ন ভগ্নাংশ (dy, dx)-এ নামিয়ে আনি। gcd দিয়ে দুজনকে ভাগ — যেমন (4, 2) হয়ে যায় (2, 1)। vertical-এ dx = 0, তখনও কোনো crash নেই।

    if dx < 0 or (dx == 0 and dy < 0):
        dy, dx = -dy, -dx

চিহ্ন এক রকম রাখার জন্য — যেন (1, 2) আর (-1, -2) একই slope হিসেবে মেলে।

def slope_value(a, b):
    if dx == 0:
        return None
    return (b[1] - a[1]) / dx

এখানে শুধু আসল সংখ্যাটা ছাপতে হলে ভাগ করি — কিন্তু আগে dx == 0 চেক করে vertical হলে None ফেরাই, যাতে crash না হয়।

বাকি assert লাইনগুলো নিজেদের যাচাই করছে; সব মিললে শেষে সব test pass! ছাপে।

14. Output walkthrough

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

True
False
(2, 3)
সব test pass!

প্রথম লাইন: (0,0),(1,1),(2,2) এক লাইনে → True। দ্বিতীয়: (0,0),(1,1),(2,3) এক লাইনে নয় → False। তৃতীয়: (1,1)→(4,3)-এর slope ভগ্নাংশে (2,3)। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(1) — collinearity check-এ কয়েকটা বিয়োগ-গুণ-তুলনা, ব্যস। slope_fraction-এ gcd-টা সংখ্যার আকারে log, তবু কার্যত ধ্রুবক।

16. Space complexity

O(1) — শুধু গুটিকয় variable (dx, dy, g)। কোনো বাড়তি list/array নেই।

17. Common mistakes

  1. slope ভাগ করে collinearity দেখা — dx = 0 হলে ZeroDivisionError; সবসময় cross multiplication।
  2. float slope == দিয়ে মেলানো — 0.1+0.2 != 0.3 জাতীয় ফাঁদে ভুল উত্তর; integer cross-product-এ এই সমস্যা নেই।
  3. degenerate case (দুটো point একই) ভুলে যাওয়া — A == B হলে cross product 0, তাই collinear ধরা পড়ে; কিন্তু slope সংজ্ঞাহীন, মনে রাখো।
  4. চিহ্ন গুলিয়ে ফেলা — cross multiplication-এ দুই পাশ একই গঠনে রাখো (left = right); এদিক-ওদিক করলে চিহ্নে ভুল।
  5. এই check-কে শুধু collinearity ভাবা — আসলে এই রাশির চিহ্নও অর্থপূর্ণ (orientation); 116-এ সেটাই কাজে লাগবে, তাই গঠনটা মনে রাখো।

18. Harder problems that inherit this idea

  • LeetCode — Max Points on a Line (https://leetcode.com/problems/max-points-on-a-line/) — একই লাইনে সবচেয়ে বেশি point; slope তুলনা cross-multiplication/gcd দিয়ে precision-নিরাপদ রাখা মূল চ্যালেঞ্জ।
  • LeetCode — Check If It Is a Straight Line (https://leetcode.com/problems/check-if-it-is-a-straight-line/) — সব point এক লাইনে কি না — এই collinearity test-এরই সরাসরি প্রয়োগ।
  • 116 (Orientation of Three Points) — এই repo-রই পরের ধাপ, যেখানে cross product-এর চিহ্ন CW/CCW/collinear বলে দেবে।

19. Pattern learned

Cross multiplication to avoid division — a/b == c/d-কে a*d == c*b-তে বদলে ভাগ (আর তার সাথের ZeroDivisionError ও float) পুরো এড়াও। আর গভীর শিক্ষা: collinearity check আসলে cross product = 0; এই একই রাশির চিহ্ন পরে orientation দেবে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "slope ভাগ কোরো না — collinearity = (by−ay)(cx−ax) == (cy−ay)(bx−ax), পুরো integer, কোনো ZeroDivisionError বা float-bug নেই। আর এই গুণফলটাই cross product, যার চিহ্ন পরে orientation বলবে।"

পরের ধাপ → 115 — Area of Triangle (একই cross product এবার area দেবে — shoelace)। শিকড় → 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" লেখো।