Skip to content

116 — Orientation of Three Points

এই note-টা এই পুরো level-এর হৃদপিণ্ড — সময় নিয়ে পড়ো। 114-এ cross product জিজ্ঞেস করেছে "শূন্য কি?", 115-এ "কত?"; আজ সবচেয়ে শক্তিশালী প্রশ্ন — "চিহ্ন কী?"। এই একটা চিহ্ন থেকে তুমি বলে দিতে পারবে তিনটা point ঘড়ির কাঁটার দিকে নাকি উল্টো দিকে বাঁক নিয়েছে। Segment intersection (117) আর convex hull (120) — দুটোরই ভিত্তি এই একটা ধারণা।

Source

  • Original source: CP-Algorithms — Oriented area of a triangle
  • Platform: CP-Algorithms — https://cp-algorithms.com/geometry/oriented-triangle-area.html
  • 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, এবার মান নয়, চিহ্ন)

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-এর "ঘোরার দিক" বলে দেয়।

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-এ লিখে রাখো।

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 চিরকালের বন্ধু।

4. Real-life analogy

ভাবো তুমি গাড়ি চালিয়ে A থেকে B-তে গেলে, তারপর B থেকে C-তে যেতে হবে। স্টিয়ারিং কোন দিকে ঘোরালে?

  • বাঁ দিকে ঘোরালে (CCW) — তুমি ঘড়ির কাঁটার উল্টো দিকে বাঁকছ
  • ডান দিকে ঘোরালে (CW) — ঘড়ির কাঁটার দিকে
  • একদম সোজা চললে (কোনো বাঁক নেই) — তিন জায়গা এক সরলরেখায়, collinear

Orientation function ঠিক এই "স্টিয়ারিং কোন দিকে?" প্রশ্নের উত্তর — শুধু একটা cross product-এর চিহ্ন দেখে। কোনো কোণ মাপতে হয় না, কোনো trig লাগে না।

5. Visual explanation

তিনটা case — cross product-এর চিহ্নই আলাদা করে দেয় (y উপরে বাড়ে):

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।

6. Example input and output

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-এর ভেতরে নয় — পুরো অসীম লাইনেই।

7. Brute force thinking

cross product না জানলে, প্রথমে slope তুলনা করে বা কোণ মেপে ভাবতে পারো:

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" নয় ঠিক, বরং ভঙ্গুর আর জটিল:

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-এর চিহ্ন — কোণ মাপার দরকারই নেই। তাই:

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।

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):

val = (4)*(-3) - (0)*(2) = -12 - 0 = -12
-12 < 0  ->  CW (-1)

একই A, B; শুধু C-র চিহ্ন বদলেই orientation উল্টে গেল।

12. Python solution

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

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

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-এ এ সমস্যা নেই)।

18. Harder problems that inherit this idea

  • CSES — Point Location Test (https://cses.fi/problemset/task/2189) — ঠিক এই orientation: point টা line-এর বাঁয়ে, ডানে, না উপরে।
  • CSES — Convex Hull (https://cses.fi/problemset/task/2195) — পুরো hull গড়ার ভিত্তি এই orientation (problem 120-এ আসছে)।
  • 117 (Line Intersection Basic) — এই repo-রই পরের ধাপ, যেখানে চারটা orientation মিলে segment কাটাকাটি ধরা পড়বে।

19. Pattern learned

Orientation via cross product sign — sign((b−a)×(c−a)) দিয়ে CCW/CW/collinear; কোণ বা atan2 লাগে না, integer-এ নিখুঁত। বড় শিক্ষা: এই একটা function geometry-র মেরুদণ্ড — intersection, convex hull, point-in-polygon সব এর উপর দাঁড়ায়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "orientation = cross product-এর চিহ্ন; +1 CCW, −1 CW, 0 collinear — integer-এ নিখুঁত, কোনো atan2/epsilon নেই। এই function মুখস্থ — 117 আর 120 এটা ছাড়া অচল। (screen coord-এ চিহ্ন উল্টো!)"

পরের ধাপ → 117 — Line Intersection Basic (চারটা orientation মিলে কাটাকাটি)। শিকড় → 115 — Area of Triangle। সম্পর্কিত → 120 — Convex Hull Intro।

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