Problem link ও উৎস
- **Original source:** CP-Algorithms — Oriented area of a triangle
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Medium
- **Pattern:** cross product sign
- **Basic idea inherited from:** 115 — Area of Triangle (একই cross product, এবার মান নয়, চিহ্ন)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তিনটা point দেওয়া — `A`, `B`, `C` — এই ক্রমে। বলতে হবে A থেকে B, তারপর B থেকে C — এই পথে হাঁটলে তুমি কোন দিকে বাঁক নিচ্ছ:
- **counter-clockwise (CCW)** — বাঁ দিকে বাঁক (ঘড়ির কাঁটার উল্টো) → আমরা বলব `+1`
- **clockwise (CW)** — ডান দিকে বাঁক (ঘড়ির কাঁটার দিকে) → `−1`
- **collinear** — কোনো বাঁকই নেই, তিনজন এক সরলরেখায় → `0`
ব্যস, একটা সংখ্যা — `+1`, `−1`, বা `0` — যেটা তিন point-এর "ঘোরার দিক" বলে দেয়।
### Input ও output {#6-example-input-and-output}
```text
A B C val orientation
----------------------------------------------------
(0,0) (4,0) (2,3) 12 +1 (CCW, C উপরে)
(0,0) (4,0) (2,-3) -12 -1 (CW, C নিচে)
(0,0) (4,0) (2,0) 0 0 (collinear, AB লাইনেই)
(0,0) (1,1) (2,2) 0 0 (collinear)
(0,0) (0,4) (2,2) -8 -1 (vertical AB-তেও কাজ করে)
(0,0) (4,0) (5,0) 0 0 (B-র বাইরেও collinear → 0)
```
খেয়াল করো: শুধু চিহ্নই গুরুত্বপূর্ণ, মান (12 বা 8) নয়; vertical AB-তেও কোনো special case লাগে না (ভাগ নেই); আর collinear মানে শুধু segment-এর ভেতরে নয় — পুরো অসীম লাইনেই।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি গাড়ি চালিয়ে A থেকে B-তে গেলে, তারপর B থেকে C-তে যেতে হবে। স্টিয়ারিং কোন দিকে ঘোরালে?
- বাঁ দিকে ঘোরালে (CCW) — তুমি ঘড়ির কাঁটার উল্টো দিকে বাঁকছ
- ডান দিকে ঘোরালে (CW) — ঘড়ির কাঁটার দিকে
- একদম সোজা চললে (কোনো বাঁক নেই) — তিন জায়গা এক সরলরেখায়, collinear
Orientation function ঠিক এই "স্টিয়ারিং কোন দিকে?" প্রশ্নের উত্তর — শুধু একটা cross product-এর চিহ্ন দেখে। কোনো কোণ মাপতে হয় না, কোনো trig লাগে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
115-এ আমরা `signed_doubled_area` বানিয়েছি — `abs` ছাড়া cross product, যার চিহ্ন রেখে দিয়েছিলাম। তখন বলেছিলাম "এই চিহ্ন পরে orientation দেবে" — সেই পরে-টা এখন।
মানে orientation হলো 115-এর signed area-কে শুধু `sign()` দিয়ে `+1/−1/0`-তে নামিয়ে আনা। আর 114-এর collinear ছিল এর `0` case। তাই তিনটা problem একই সিঁড়ির তিন ধাপ: 114 (শূন্য?) → 115 (কত?) → 116 (চিহ্ন?)। এই ধাপটা পরিষ্কার হলে cross product চিরকালের বন্ধু।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea **cross product-এর চিহ্ন**। দুটো vector `AB` আর `AC`-এর cross product:
```
val = (Bx − Ax)(Cy − Ay) − (By − Ay)(Cx − Ax)
```
এই একটা সংখ্যার চিহ্নই পুরো গল্প (standard math axes — y উপরে বাড়ে):
- `val > 0` → C, AB তীরের **বাঁ দিকে** → CCW (`+1`)
- `val < 0` → C, AB তীরের **ডান দিকে** → CW (`−1`)
- `val == 0` → C ঠিক AB লাইনেই → collinear (`0`)
এটাই 115-এর signed doubled area — শুধু এবার মান নয়, **চিহ্ন**-টাই উত্তর। সতর্কতা: screen coordinate-এ (y নিচে বাড়ে) চিহ্ন উল্টে যায়, তাই convention একবার ঠিক করে comment-এ লিখে রাখো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
cross product না জানলে, প্রথমে slope তুলনা করে বা কোণ মেপে ভাবতে পারো:
```python
import math
def orientation_bad(a, b, c):
# AB-র কোণ আর AC-র কোণ বের করে পার্থক্য দেখি
ang_ab = math.atan2(b[1] - a[1], b[0] - a[0])
ang_ac = math.atan2(c[1] - a[1], c[0] - a[0])
diff = ang_ac - ang_ab
# diff কে -pi..pi-তে আনি
while diff > math.pi: diff -= 2 * math.pi
while diff < -math.pi: diff += 2 * math.pi
if diff > 1e-12: return 1
if diff < -1e-12: return -1
return 0
```
এটা মোটামুটি কাজ করে, কিন্তু `atan2` float, wrap-around handle করতে হয়, আর `1e-12`-র মতো জাদুসংখ্যা দিয়ে "শূন্য কাছাকাছি" ঠিক করতে হয় — সবই precision-ফাঁদ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
"slow" নয় ঠিক, বরং **ভঙ্গুর আর জটিল**:
```text
atan2 পথ: float কোণ -> wrap-around -> epsilon দিয়ে শূন্য চেক
-> collinear-এ atan2 প্রায় সমান কিন্তু ঠিক সমান নয়
-> ভুল 0 / ভুল ±1 হতে পারে
cross পথ: একটা integer গুণফলের চিহ্ন
-> val == 0 ঠিক ঠিক collinear, কোনো epsilon লাগে না
```
cross product integer হলে চিহ্ন নিখুঁত — `val == 0` মানে precisely collinear, কোনো "কাছাকাছি শূন্য" আন্দাজ করতে হয় না। atan2 সেই নিশ্চয়তা দিতে পারে না।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **"কোন দিকে বাঁক" = cross product-এর চিহ্ন — কোণ মাপার দরকারই নেই।** তাই:
```python
def orientation(a, b, c):
val = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if val > 0: return 1 # CCW
if val < 0: return -1 # CW
return 0 # collinear
```
একটা integer গুণফল, তার চিহ্ন — ব্যস। atan2 নেই, epsilon নেই, wrap-around নেই। এটাই geometry-র সবচেয়ে কাজের একটা function।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **দুটো তীরের আপেক্ষিক ঘোরার দিক জানতে কোণ লাগে না — একটা cross product-এর চিহ্নই বলে দেয়।**
আর গভীর tweak — **cross product একই, প্রশ্নটাই শুধু বদলায়:** `== 0`? (collinearity, 114), `abs`? (area, 115), `sign`? (orientation, 116)। এই function-টা একবার লিখে মুখস্থ করে নাও; 117-এ segment intersection আর 120-এ convex hull — দুটোই এটাকে ছাড়া নড়বে না। এটাই level-এর কেন্দ্রীয় building block।
### ছবিতে বোঝা {#5-visual-explanation}
তিনটা case — cross product-এর চিহ্নই আলাদা করে দেয় (y উপরে বাড়ে):
```text
CCW (+1): CW (-1): collinear (0):
y y y
3 | C(2,3) 0 | A----B 3 | C(2,2)
2 | / -1| \ 2 | B(... on line)
1 | / বাঁ বাঁক -2| \ ডান 1 | A(... on line)
0 | A----B -3| C(2,-3) +----------- x
+--------- x +--------- x A, B, C এক লাইনে
A(0,0) B(4,0) C(2,3) A(0,0) B(4,0) C(2,-3)
val = 4*3 - 0*2 val = 4*(-3) - 0*2 val = 4*2 - 0*2... না:
= 12 > 0 CCW = -12 < 0 CW A,B,C collinear হলে 0
```
লক্ষ করো — একই A, B; শুধু C উপরে (CCW) না নিচে (CW), তাতেই চিহ্ন উল্টে যায়। এই চিহ্নটাই orientation।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `A=(0,0)`, `B=(4,0)`, `C=(2,3)` নিয়ে orientation বের করি:
1. শুরুর অবস্থা: A=(0,0), B=(4,0), C=(2,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 = 2 − 0 = 2`
7. দ্বিতীয় গুণ: `0 * 2 = 0`
8. `val = 12 − 0 = 12`
9. `val > 0`? হ্যাঁ → **CCW (+1)**
এবার C নিচে নামাই, `C=(2,−3)`:
```text
val = (4)*(-3) - (0)*(2) = -12 - 0 = -12
-12 < 0 -> CW (-1)
```
একই A, B; শুধু C-র চিহ্ন বদলেই orientation উল্টে গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def orientation(a, b, c):
"""A->B->C পথে বাঁকের দিক: +1 = CCW, -1 = CW, 0 = collinear।
Convention: standard math axes (y উপরে বাড়ে)। screen coord হলে চিহ্ন উল্টো।"""
val = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if val > 0:
return 1
if val < 0:
return -1
return 0
def turn_name(a, b, c):
"""মানুষ-পড়ার মতো নাম।"""
o = orientation(a, b, c)
return {1: "CCW", -1: "CW", 0: "collinear"}[o]
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert orientation((0, 0), (4, 0), (2, 3)) == 1 # CCW
assert orientation((0, 0), (4, 0), (2, -3)) == -1 # CW
assert orientation((0, 0), (4, 0), (2, 0)) == 0 # collinear (segment-এ)
assert orientation((0, 0), (1, 1), (2, 2)) == 0 # collinear
assert orientation((0, 0), (4, 0), (5, 0)) == 0 # collinear (segment-এর বাইরে)
assert orientation((0, 0), (0, 4), (2, 2)) == -1 # vertical AB, C ডানে -> CW
assert orientation((0, 0), (0, 4), (-2, 2)) == 1 # vertical AB, C বাঁয়ে -> CCW
# মান নয়, চিহ্নই গুরুত্বপূর্ণ: বড় হোক বা ছোট, একই উত্তর
assert orientation((0, 0), (100, 0), (50, 1)) == 1 # সামান্য উপরেও CCW
assert turn_name((0, 0), (4, 0), (2, 3)) == "CCW"
assert turn_name((0, 0), (4, 0), (2, 0)) == "collinear"
print(orientation((0, 0), (4, 0), (2, 3))) # 1
print(orientation((0, 0), (4, 0), (2, -3))) # -1
print(turn_name((0, 0), (4, 0), (2, 0))) # collinear
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def orientation(a, b, c):
val = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
```
এটাই হৃদয় — দুটো vector `AB = (b−a)` আর `AC = (c−a)`-এর cross product। `(Bx−Ax)(Cy−Ay)` থেকে `(By−Ay)(Cx−Ax)` বিয়োগ। পুরোটা integer।
```
if val > 0:
return 1
if val < 0:
return -1
return 0
```
শুধু চিহ্ন দেখছি: ধনাত্মক → CCW (+1), ঋণাত্মক → CW (−1), শূন্য → collinear (0)। মান কত তাতে কিছু আসে যায় না।
```
def turn_name(a, b, c):
o = orientation(a, b, c)
return {1: "CCW", -1: "CW", 0: "collinear"}[o]
```
কেবল মানুষ-পড়ার সুবিধার্থে নামে রূপান্তর — dictionary দিয়ে `+1/−1/0` থেকে শব্দ।
বাকি `assert` লাইনগুলো নিজেদের যাচাই করছে; সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
1
-1
collinear
সব test pass!
```
প্রথম লাইন: C উপরে → CCW → 1। দ্বিতীয়: C নিচে → CW → −1। তৃতীয়: (0,0),(4,0),(2,0) — তিনজন x-অক্ষে → collinear। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — একটা cross product (কয়েকটা বিয়োগ-গুণ-বিয়োগ) আর একটা চিহ্ন চেক। input-নির্বিশেষে ধ্রুবক।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু একটা `val` variable। কোনো বাড়তি জায়গা নেই।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **চিহ্ন convention গুলিয়ে ফেলা** — positive = CCW *standard math axes-এ* (y উপরে); screen coordinate-এ (y নিচে) উল্টে যায়। একবার ঠিক করে comment-এ লিখে রাখো।
2. **collinear (0) case ভুলে যাওয়া** — শুধু `> 0` আর `else` লিখলে collinear ভুলভাবে CW ধরা পড়বে; তিনটা case-ই আলাদা করো।
3. **মান আর চিহ্ন গুলিয়ে ফেলা** — orientation-এ মান (12 না 8) অপ্রাসঙ্গিক, শুধু চিহ্ন; মান দরকার হলে সেটা area (115)।
4. **atan2/কোণ দিয়ে করতে গিয়ে precision-এ আটকানো** — integer cross product-এ `== 0` নিখুঁত; float কোণে epsilon ছাড়া collinear ধরা যায় না।
5. **C++/Java-তে overflow** — বড় coordinate-এ `(b−a)*(c−a)` overflow করতে পারে; সেখানে `long long`/`long` ভাবো (Python-এ এ সমস্যা নেই)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Point Location Test** (