Problem link ও উৎস
- **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-এ থাকো" দর্শন)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুই ভাগে প্রশ্ন:
- **Slope:** দুটো point `A` আর `B` দেওয়া; এদের দিয়ে যাওয়া সরলরেখার ঢাল (slope) কত — মানে x একক ডানে গেলে y কত ওঠে/নামে।
- **Collinearity:** তিনটা point `A`, `B`, `C` দেওয়া; এরা কি একই সরলরেখায় (collinear) আছে নাকি নেই?
আসল চ্যালেঞ্জ slope-এর সংখ্যাটা বের করা নয় — চ্যালেঞ্জ হলো **ভাগ না করে, error ছাড়া, float ছাড়া** এই প্রশ্নগুলোর উত্তর দেওয়া।
### Input ও output {#6-example-input-and-output}
```text
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 করতে হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পাহাড়ি রাস্তার ঢাল মাপছ — "প্রতি 4 মিটার সামনে গেলে 2 মিটার ওঠে।" তুমি বলতে পারো ঢাল `2/4 = 0.5`। কিন্তু একটা জায়গায় রাস্তা একদম খাড়া দেয়াল — সামনে 0 মিটার, উপরে 5 মিটার। তখন `5/0`? অর্থহীন! ঢাল "অসীম"।
Collinearity-তে আমরা চালাকি করি: দুটো ঢাল মেলানোর বদলে জিজ্ঞেস করি "প্রথম রাস্তার (সামনে, উপরে) আর দ্বিতীয়টার (সামনে, উপরে) কি একই অনুপাতে?" — সেটা ভাগ ছাড়াই cross গুণে মেলানো যায়। খাড়া দেয়াল (vertical) হোক বা না হোক, গুণে কোনো অসুবিধা নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
113-এ আমরা শিখেছি দূরত্ব তুলনায় sqrt বাদ দিয়ে integer-এ থাকার মূল্য। এই problem সেই একই দর্শনের আরেকটা রূপ — কিন্তু এবার শত্রু sqrt নয়, **ভাগ**।
113-এর শিক্ষা ছিল: "float এড়াও, যতক্ষণ পারো integer-এ থাকো।" এখানে সেটাই প্রয়োগ করছি slope-এ — ভাগ (যা float আর ZeroDivisionError আনে) সরিয়ে গুণে নামিয়ে আনছি। মানে দুটো problem একই বড় নিয়মের দুই উদাহরণ: **precision-নিরাপদ থাকতে চাইলে float-জন্মদানকারী operation (sqrt, ভাগ) যথাসম্ভব দেরিতে, বা একেবারেই নয়।**
### ভেতরের অঙ্ক {#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 হয়ে ফিরবে।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যা মাথায় আসে — স্কুলের সূত্র সরাসরি, ভাগ করে slope মিলিয়ে:
```python
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" নয়, বরং **ভুল আর ভঙ্গুর** — যেটা আরও বিপজ্জনক:
```text
সমস্যা 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 গুণে ভাগ ছাড়াই বলা যায়:
```python
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-এর প্রথম পরিচয়।
### ছবিতে বোঝা {#5-visual-explanation}
তিনটা point একই লাইনে থাকলে A→B তীর আর A→C তীর একই দিকে নির্দেশ করে — অনুপাত মেলে:
```text
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), তাই বাঁকা। কোথাও ভাগ করিনি।
### ছোট input-এ ধাপে ধাপে {#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 করত:
```text
বাঁ পাশ: (5-0)*(0-0) = 5*0 = 0
ডান পাশ: (9-0)*(0-0) = 9*0 = 0
0 == 0 ✓ -> collinear, কোনো crash ছাড়াই
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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!` ছাপে।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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-এ সেটাই কাজে লাগবে, তাই গঠনটা মনে রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Max Points on a Line** (