Problem link ও উৎস
- **Original source:** Classic exercise (school triangle area, shoelace/determinant রূপে)
- **Platform:** Classic exercise (polygon area সব geometry set-এ আছে)
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Easy
- **Pattern:** shoelace
- **Basic idea inherited from:** 114 — Slope and Collinearity (একই cross product রাশি, এবার মান = area)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তিনটা point দেওয়া — `A`, `B`, `C` — এরা একটা triangle-এর তিন কোণা। বলতে হবে এই triangle-এর ক্ষেত্রফল (area) কত।
দুটো রূপ দরকার হতে পারে:
- **doubled area** — area-র দ্বিগুণ, যেটা সবসময় integer (যদি point-গুলো integer হয়), তুলনার জন্য আদর্শ
- **আসল area** — সেই doubled area-কে 2 দিয়ে ভাগ, যেমন 6.0 বা 7.5
আর base × height-এর সেই পুরনো ঝামেলা (height বের করতে দূরত্ব, লম্ব...) — এসব ছাড়াই, শুধু coordinate থেকে সরাসরি।
### Input ও output {#6-example-input-and-output}
```text
A B C 2*area area
---------------------------------------------------
(0,0) (4,0) (4,3) 12 6.0
(0,0) (4,0) (0,3) 12 6.0 (সমকোণী, ½*4*3 = 6)
(0,0) (2,0) (1,1) 2 1.0
(0,0) (1,1) (2,2) 0 0.0 (collinear → area 0!)
(0,0) (4,0) (2,3) 12 6.0 (CCW)
(0,0) (2,3) (4,0) -12 -> 12 6.0 (CW: signed -12, abs নিলে 12)
```
খেয়াল করো: collinear তিন point দিলে area 0 (114-এর সাথে মিলে গেল); আর point-এর ক্রম উল্টে দিলে signed area-র চিহ্ন বদলায়, কিন্তু `abs` নিলে area একই থাকে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা জমির তিন কোণায় তিনটা খুঁটি পোঁতা, আর তুমি জমিটার ক্ষেত্রফল মাপতে চাও — কিন্তু হাতে শুধু GPS coordinate, ফিতা নেই।
পুরনো উপায়: এক বাহুকে base ধরে, লম্ব দূরত্ব (height) মেপে, `½ × base × height`। কিন্তু height মাপা ঝামেলা।
Shoelace বলে: শুধু তিন কোণার coordinate দাও, আমি আড়াআড়ি গুণ করে সরাসরি area বলে দিচ্ছি — কোনো height-টিকটিকি লাগবে না। আর যদি তিন খুঁটি একই সরলরেখায় পড়ে যায়, তাহলে তো জমিই নেই (একটা সরু রেখা) — area 0।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
114-এ আমরা cross product রাশি `(Bx−Ax)(Cy−Ay) − (By−Ay)(Cx−Ax)`-এর সাথে পরিচিত হয়েছি — সেখানে শুধু দেখেছি এটা **0 কি না** (collinear)।
আজ আমরা সেই একই রাশির **মান** নিচ্ছি। 0 হলে area 0 (তিন point এক লাইনে, triangle নেই) — মানে collinearity আসলে "area = 0"-এরই আরেক নাম! তাই 114 আর 115 একই সূত্রের দুই চেহারা: 114 জিজ্ঞেস করে "শূন্য?", 115 জিজ্ঞেস করে "কত?"। এই ধারাবাহিকতা মাথায় রাখলে cross product একটাই অস্ত্র, অনেক প্রশ্নের উত্তর।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea **shoelace** (জুতার ফিতার মতো আড়াআড়ি গুণ)। তিন point A, B, C-র জন্য:
```
doubled area = |(Bx − Ax)(Cy − Ay) − (By − Ay)(Cx − Ax)|
area = doubled area / 2
```
ভেতরের রাশিটা ঠিক 114-এর cross product — দুটো vector `AB` আর `AC` দিয়ে বানানো parallelogram-এর (signed) area। triangle তার অর্ধেক, তাই `/2`। `abs` লাগে কারণ point-গুলো ঘড়ির কাঁটার দিকে (CW) সাজানো থাকলে রাশিটা negative আসে — চিহ্নটা আসলে ঘোরার দিক বলে, সেটাও কাজে লাগে (116-এ)।
সৌন্দর্য: পুরোটা integer (input integer হলে), shoelace-এর মান doubled area। আসল area দরকার হলে তবেই `/2`।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে স্কুলের `½ × base × height` মাথায় আসে। base হিসেবে AB নিয়ে, এর দৈর্ঘ্য আর C থেকে AB লাইনের লম্ব দূরত্ব দরকার:
```python
import math
def area_bad(a, b, c):
base = math.dist(a, b) # AB-র দৈর্ঘ্য (sqrt!)
# C থেকে AB লাইনের লম্ব দূরত্ব — line equation দিয়ে
num = abs((b[1]-a[1])*c[0] - (b[0]-a[0])*c[1] + b[0]*a[1] - b[1]*a[0])
den = math.dist(a, b) # আবার sqrt
height = num / den
return 0.5 * base * height
```
এটা ঠিক উত্তরই দেয়, কিন্তু দুটো sqrt আর একটা ভাগ — তিনটাই float, আর height-এর সূত্রটা মনে রাখাও কঠিন।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
"slow" নয় ঠিক, বরং **অপ্রয়োজনীয় float আর জটিল**:
```text
brute force: base = sqrt(...), height = num / sqrt(...)
-> base * height-এ sqrt গুলো কাটাকাটি যায়,
মানে আমরা ঘুরিয়ে আসলে num/2-ই পাচ্ছি!
shoelace : সরাসরি |cross| / 2 (কোনো sqrt নেই, integer doubled area)
```
মজার ব্যাপার — brute force-এ base × height করলে sqrt গুলো নিজেরাই কাটাকাটি হয়ে যায়, আর হাতে থাকে ঠিক shoelace-এর `|cross|/2`। তাহলে sqrt-এর ঝামেলায় গিয়ে লাভ কী? সরাসরি cross product নাও।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **triangle area = parallelogram area-র অর্ধেক, আর parallelogram area = cross product-এর মান।** তাই height-টিকটিকি বাদ, সরাসরি:
```python
def doubled_area(a, b, c):
return abs((b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0]))
```
`abs` নেওয়ার আগের রাশিটা signed (ঘোরার দিকসহ); area চাইলে `abs`, তারপর `/2`। যতক্ষণ পারো doubled area-তেই থাকো — integer, নিখুঁত।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **area-কে অর্ধেক না করে "doubled area"-তেই কাজ চালাও — integer থাকে, আর `/2` শুধু একদম শেষে, যদি আসল মান ছাপতে হয়।**
আর তার চেয়েও বড় tweak — **collinearity, area, orientation সব একই cross product।** 114 জিজ্ঞেস করেছে "শূন্য কি?", 115 জিজ্ঞেস করছে "কত?", আর 116 জিজ্ঞেস করবে "চিহ্ন কী?"। তিন প্রশ্ন, এক রাশি। এই ঐক্যটা ধরতে পারলে geometry অনেক হালকা লাগবে।
### ছবিতে বোঝা {#5-visual-explanation}
cross product = AB আর AC দিয়ে বানানো parallelogram-এর area; triangle তার ঠিক অর্ধেক:
```text
y
3 | C(4,3)
2 | / \
1 | / tri \ AB = (4,0), AC = (4,3)
0 | A(0,0)----B(4,0) cross = 4*3 - 0*4 = 12
+------------------ x doubled area = 12
0 1 2 3 4 area = 12 / 2 = 6.0
parallelogram (AB, AC): area 12 ┐
triangle ABC : area 6 ┘ ঠিক অর্ধেক
```
লক্ষ করো — cross product 12 হলো parallelogram-এর পুরো area (= doubled triangle area), আর triangle তার অর্ধেক, 6। এই "doubled-এ থাকো, শেষে অর্ধেক" অভ্যাসটা integer-নিরাপদ।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `A=(0,0)`, `B=(4,0)`, `C=(4,3)` নিয়ে area বের করি:
1. শুরুর অবস্থা: A=(0,0), B=(4,0), C=(4,3)
2. `Bx − Ax = 4 − 0 = 4`
3. `Cy − Ay = 3 − 0 = 3`
4. প্রথম গুণ: `4 * 3 = 12`
5. `By − Ay = 0 − 0 = 0`
6. `Cx − Ax = 4 − 0 = 4`
7. দ্বিতীয় গুণ: `0 * 4 = 0`
8. cross = `12 − 0 = 12` (signed)
9. doubled area = `abs(12) = 12`
10. শেষ অবস্থা: আসল area `= 12 / 2 = 6.0`
প্রতিটা ধাপ integer; শুধু ধাপ 10-এ এসে `/2`। collinear হলে ধাপ 8-এ cross = 0 আসত → area 0।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def doubled_area(a, b, c):
"""triangle ABC-র ক্ষেত্রফলের দ্বিগুণ (integer থাকে) — abs নেওয়া।"""
return abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]))
def signed_doubled_area(a, b, c):
"""signed (চিহ্নসহ) doubled area — চিহ্ন ঘোরার দিক বলে (116-এ লাগবে)।"""
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
def triangle_area(a, b, c):
"""আসল ক্ষেত্রফল — শুধু এখানে এসে 2 দিয়ে ভাগ।"""
return doubled_area(a, b, c) / 2
def is_degenerate(a, b, c):
"""area 0 মানে তিন point এক লাইনে — triangle-ই নেই।"""
return doubled_area(a, b, c) == 0
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert doubled_area((0, 0), (4, 0), (4, 3)) == 12
assert doubled_area((0, 0), (4, 0), (0, 3)) == 12 # সমকোণী
assert doubled_area((0, 0), (2, 0), (1, 1)) == 2
assert doubled_area((0, 0), (1, 1), (2, 2)) == 0 # collinear -> 0
assert triangle_area((0, 0), (4, 0), (4, 3)) == 6.0
assert triangle_area((0, 0), (2, 0), (1, 1)) == 1.0
# চিহ্ন: CCW ধনাত্মক, CW ঋণাত্মক, কিন্তু মান এক
assert signed_doubled_area((0, 0), (4, 0), (2, 3)) == 12 # CCW
assert signed_doubled_area((0, 0), (2, 3), (4, 0)) == -12 # CW (উল্টো ক্রম)
assert is_degenerate((0, 0), (1, 1), (2, 2)) is True # এক লাইনে
assert is_degenerate((0, 0), (4, 0), (4, 3)) is False
print(doubled_area((0, 0), (4, 0), (4, 3))) # 12
print(triangle_area((0, 0), (4, 0), (4, 3))) # 6.0
print(is_degenerate((0, 0), (1, 1), (2, 2))) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def doubled_area(a, b, c):
return abs((b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]))
```
ভেতরের রাশি ঠিক 114-এর cross product — AB আর AC দিয়ে বানানো parallelogram-এর signed area। `abs` নিয়ে আমরা মান পাই, যা triangle-এর দ্বিগুণ ক্ষেত্রফল। পুরোটা integer।
```
def signed_doubled_area(a, b, c):
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
```
`abs` ছাড়া — চিহ্নটা রেখে দিই। ধনাত্মক মানে CCW, ঋণাত্মক মানে CW। 116-এ এই চিহ্নই orientation দেবে।
```
def triangle_area(a, b, c):
return doubled_area(a, b, c) / 2
```
আসল area চাইলে এখানেই, একদম শেষে, 2 দিয়ে ভাগ — তাই দরকারে float।
```
def is_degenerate(a, b, c):
return doubled_area(a, b, c) == 0
```
doubled area 0 মানে তিন point এক লাইনে (114-এর collinear!) — তাই triangle নেই।
বাকি `assert` লাইনগুলো নিজেদের যাচাই করছে; সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
12
6.0
True
সব test pass!
```
প্রথম লাইন: doubled area 12 (integer)। দ্বিতীয়: আসল area 6.0। তৃতীয়: (0,0),(1,1),(2,2) এক লাইনে → degenerate → True। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — তিনটা point-এর জন্য কয়েকটা বিয়োগ-গুণ-বিয়োগ। (n-কোণা polygon-এ shoelace হবে O(n) — প্রতিটা ধার একবার, যেটা 124-এ লাগবে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু গুটিকয় মান হিসাব করছি, কোনো বাড়তি list/array নেই।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`abs` নিতে ভুলে যাওয়া** — CW ক্রমে রাশি negative আসে; area চাইলে `abs`, নাহলে ঋণাত্মক area পাবে।
2. **`/2` নিতে ভুলে যাওয়া** — cross product হলো *doubled* area; আসল area অর্ধেক।
3. **খুব তাড়াতাড়ি `/2` করে float-এ চলে যাওয়া** — যতক্ষণ পারো doubled (integer)-এ থাকো; তুলনা/যোগে এটা নিরাপদ, ভাগ শুধু একদম শেষে।
4. **collinear case ভুলে যাওয়া** — তিন point এক লাইনে হলে area 0; এটা ভুল নয়, এটাই সঠিক (triangle নেই)।
5. **point-এর ক্রম নিয়ে দুশ্চিন্তা** — area-র জন্য ক্রম গুরুত্বহীন (abs নিলে); শুধু signed দরকার হলেই ক্রম/চিহ্ন খেয়াল রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Polygon Area** (