Skip to content

120 — Convex Hull Intro

এই note-টা level-এর প্রথম Hard, কিন্তু ভয় পেও না — এর ভেতরের ইঞ্জিন তোমার চেনা। 116-এর orientation একবার ভালো করে গাঁথা থাকলে convex hull আসলে "sort করো, তারপর ভুল বাঁকে point pop করো" — এইটুকুই। ছবিটা মাথায় রাখো: মেঝেতে পেরেক পোঁতা, চারদিক থেকে একটা রবার ব্যান্ড টেনে ছেড়ে দিলে যে আকার বাইরের পেরেকগুলোতে আটকে যায় — সেটাই hull। আমরা Andrew-র monotone chain দিয়ে সেটা integer-এ গড়ব।

Source

  • Original source: CP-Algorithms — Convex Hull (Andrew's monotone chain)
  • Platform: CP-Algorithms — https://cp-algorithms.com/geometry/convex-hull.html, CSES Convex Hull — https://cses.fi/problemset/task/2195
  • Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
  • Difficulty: Hard
  • Pattern: monotone chain
  • Basic idea inherited from: 116 — Orientation of Three Points (pop হবে কি না, orientation চিহ্নই বলে)

1. Problem in simple words

কতগুলো point দেওয়া (একটা list of (x, y))। বলতে হবে এদের সবাইকে ঘিরে রাখা সবচেয়ে ছোট উত্তল (convex) বহুভুজ-এর কোণাগুলো (vertices) কী কী।

"উত্তল" মানে — বহুভুজটার কোনো খাঁজ নেই, সব কোণ বাইরের দিকে ফোলা। আর "সবচেয়ে ছোট" মানে — এমন বহুভুজ যেটা সব point ভেতরে (বা সীমানায়) রাখে কিন্তু একটুও বেশি জায়গা নেয় না। বাকি ভেতরের point গুলো hull-এ থাকে না; শুধু একদম বাইরের point গুলোই কোণা হয়।

2. What is the math idea?

মূল idea Andrew's monotone chain — orientation দিয়ে দুটো অর্ধেক hull গড়া:

1. point গুলো (x, তারপর tie-তে y) দিয়ে sort করো
2. lower hull: বাঁ থেকে ডানে হেঁটে point যোগ করো; নতুন point নিয়ে
   শেষ দুটোর সাথে বাঁক যদি বাঁ-দিকে (CCW) না হয়, আগেরটা pop
3. upper hull: ডান থেকে বাঁয়ে একইভাবে
4. দুটো জোড়ো (জোড়ার endpoint দুবার গুনো না)

"pop হবে কি না" — সেটা ঠিক করে 116-এর orientation। যদি শেষ দুই point আর নতুন point মিলে CCW না হয় (মানে clockwise বা collinear), তাহলে মাঝের point টা hull-এর ভেতরে পড়ে গেছে, তাকে pop। পুরোটা integer cross product — কোনো float নেই।

3. Which basic idea does this inherit from?

116-এ আমরা orientation(a, b, c) বানিয়ে শিখেছি cross product-এর চিহ্ন দিয়ে CCW/CW/collinear বলা। তখন বলেছিলাম "120 এটা ছাড়া অচল" — এখানেই সেই দাবির পূর্ণ রূপ।

Convex hull-এর পুরো সিদ্ধান্ত — "এই point কি সীমানায় থাকবে, নাকি আগেরটা ভেতরে পড়ে গেছে?" — একটাই প্রশ্ন: শেষ তিন point-এর orientation কী। CCW হলে রাখো, নাহলে pop। তাই hull আসলে orientation-কে বারবার ডাকা একটা stack-process। 116 যত পরিষ্কার, 120 তত সহজ। (আর sort-এর অভ্যাস আসে Level 8 থেকে — দুটো ভিত্তি মিলেই এই algorithm।)

4. Real-life analogy

ভাবো একটা কাঠের তক্তায় এলোমেলো কতগুলো পেরেক পোঁতা। তুমি একটা বড় রবার ব্যান্ড নিয়ে সবগুলো পেরেকের চারপাশে টেনে ধরে ছেড়ে দিলে। রবার ব্যান্ডটা ভেতরের দিকে যতটা পারে গুটিয়ে আসবে, কিন্তু একদম বাইরের পেরেকগুলোতে আটকে যাবে — আর যে আকার নেবে সেটাই convex hull।

ভেতরের পেরেকগুলো? রবার তাদের ছোঁয়েও না — তারা hull-এর অংশ নয়। monotone chain আসলে এই গুটিয়ে আসাটাই অনুকরণ করে: একটা একটা পেরেক ধরে এগোয়, আর যখন দেখে কোনো পেরেক ভেতরে পড়ে গেছে (রবার সেখানে আটকাবে না, "ভুল দিকে বাঁক"), তখন তাকে বাদ (pop) দেয়।

5. Visual explanation

ভেতরের point গুলো বাদ পড়ে, শুধু বাইরের খোলস থাকে:

সব point:                       convex hull (রবার ব্যান্ড):
y                               y
4 |   B         E               4 |   B---------E
3 |       *  *                  3 |   |  (ভেতরের * গুলো       \
2 |   A   *      D              2 |   A    বাদ পড়ল)           D
1 |       *                     1 |   |                      /
0 |   C---------F               0 |   C---------------------F
  +-------------------- x         +-------------------- x

* = ভেতরের point (hull-এ নেই)    hull = A,B,E,D,F,C ঘিরে

pop-এর নিয়ম (orientation):
শেষ দুই point P,Q; নতুন R
orientation(P,Q,R) > 0 (CCW)? রাখো (বাঁয়ে বাঁক = খোলস ঠিক)
নাহলে (CW বা collinear)? Q-কে pop  (Q ভেতরে পড়ে গেছে)

লক্ষ করো — মাঝখানের * point গুলো রবার ব্যান্ড ছোঁয় না, তাই hull-এ নেই। কোন point থাকবে, কোনটা pop হবে — পুরোটাই orientation-এর চিহ্ন বলে দেয়।

6. Example input and output

points                                   convex hull (CCW ক্রমে)
------------------------------------------------------------------
[(0,0),(4,0),(4,4),(0,4),(2,2)]          [(0,0),(4,0),(4,4),(0,4)]
   (বর্গ + কেন্দ্রের point)                 (কেন্দ্রের (2,2) বাদ পড়ল)

[(0,0),(1,1),(2,2)]                       [(0,0),(2,2)]
   (সব এক লাইনে)                          (collinear -> শুধু দুই প্রান্ত)

[(0,0),(2,0)]                             [(0,0),(2,0)]
   (মাত্র দুটো point)                      (যা আছে তাই)

[(0,0),(3,1),(1,4),(4,4),(2,2)]          [(0,0),(3,1),(4,4),(1,4)]
   ((2,2) ভেতরে)                         (ভেতরের (2,2) বাদ)

খেয়াল করো তিনটে edge case: ভেতরের point বাদ পড়ে; সব collinear হলে hull মানে শুধু দুই প্রান্ত (একটা রেখাংশ); আর n ≤ 2 হলে যা point আছে তাই hull। এই তিনটে আগে handle না করলে algorithm ভেঙে পড়ে।

7. Brute force thinking

orientation-চালিত chain না জানলে, প্রথমে "প্রতিটা সম্ভাব্য edge পরীক্ষা" (gift wrapping-এর কাঁচা রূপ বা সব জোড়া) মাথায় আসে:

def hull_brute(points):
    pts = list(set(points))
    hull_edges = []
    n = len(pts)
    # প্রতিটা জোড়া (A, B) দেখি — বাকি সব point কি AB-র এক পাশে?
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            a, b = pts[i], pts[j]
            all_left = True
            all_right = True
            for k in range(n):
                if k == i or k == j:
                    continue
                o = orientation(a, b, pts[k])
                if o > 0: all_right = False
                if o < 0: all_left = False
            if all_left or all_right:   # AB একটা hull edge
                hull_edges.append((a, b))
    return hull_edges

এটা hull-এর edge গুলো খুঁজে দেয় (প্রতিটা hull edge-এর এক পাশে সব point থাকে), কিন্তু তিনটা nested loop।

8. Why brute force may be slow

প্রতিটা জোড়ার জন্য বাকি সব point দেখা মানে তিন স্তরের loop:

n point হলে:
  brute force: প্রতিটা জোড়া (n²) × বাকি সব point (n) = O(n³)
  monotone chain: sort O(n log n) + একবার হাঁটা O(n) = O(n log n)

n = 1000 হলে:
  O(n³) ≈ 1,000,000,000 ধাপ   (TLE)
  O(n log n) ≈ 10,000 ধাপ     (চোখের নিমেষে)

মূল অপচয় — একই point বারবার দেখা, প্রতিটা সম্ভাব্য edge-এর জন্য পুরো set scan। monotone chain sort করে একবারে বাঁ-থেকে-ডান হেঁটে stack দিয়ে এই পুনরাবৃত্তি কাটিয়ে দেয়।

9. Better thinking

মূল insight: sort করলে point গুলো একটা সরল ক্রমে আসে; তখন বাঁ-থেকে-ডান হেঁটে শুধু শেষ দুই point-এর সাথে বাঁক দেখে সিদ্ধান্ত নেওয়া যায় — ভুল বাঁকে pop। এটাই monotone chain:

def convex_hull(points):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    def build(seq):
        chain = []
        for p in seq:
            while len(chain) >= 2 and orientation(chain[-2], chain[-1], p) <= 0:
                chain.pop()              # বাঁ-বাঁক নয় -> মাঝের point ভেতরে
            chain.append(p)
        return chain
    lower = build(pts)
    upper = build(pts[::-1])
    return lower[:-1] + upper[:-1]       # জোড়ার endpoint দুবার নয়

sort O(n log n), বাকি O(n) — মোট O(n log n)। <= 0 মানে CCW ছাড়া (CW বা collinear) সব ক্ষেত্রে pop, তাই hull-এ collinear point থাকে না।

10. Thinking tweak

আসল "আহা!": এলোমেলো point-এর কঠিন আকার গড়তে আগে sort করে নাও — তখন প্রতিটা নতুন point-এর সিদ্ধান্ত শুধু একটা local প্রশ্ন: "শেষ বাঁকটা কি ঠিক দিকে?" ভুল দিকে হলে আগেরটা pop, ব্যস।

আর দ্বিতীয় tweak — পুরো hull-কে দুই অর্ধে ভাঙো (lower + upper)। উপর আর নিচের খোলস আলাদা করে একই নিয়মে গড়া অনেক সহজ, তারপর জুড়ে দাও। এই "sort + stack, ভুল বাঁকে pop" কাঠামোটা শুধু hull নয় — largest rectangle in histogram, monotonic stack-জাতীয় অনেক problem-এর হাড়। এখানে সেটা cross product-এর সাথে মিলেছে।

11. Step-by-step dry run

চলো [(0,0),(2,0),(2,2),(0,2),(1,1)] (বর্গ + কেন্দ্র) নিয়ে lower hull গড়ি:

  1. sort: [(0,0),(0,2),(1,1),(2,0),(2,2)]
  2. chain = []; নাও (0,0) → chain = [(0,0)]
  3. নাও (0,2) → chain = [(0,0),(0,2)]
  4. নাও (1,1): orientation((0,0),(0,2),(1,1)) = (0)(1) − (2)(1) = −2 ≤ 0 → pop (0,2); chain = [(0,0)]; এখন len < 2, যোগ → [(0,0),(1,1)]
  5. নাও (2,0): orientation((0,0),(1,1),(2,0)) = (1)(0) − (1)(2) = −2 ≤ 0 → pop (1,1); chain = [(0,0)]; যোগ → [(0,0),(2,0)]
  6. নাও (2,2): orientation((0,0),(2,0),(2,2)) = (2)(2) − (0)(2) = 4 > 0 → রাখো; chain = [(0,0),(2,0),(2,2)]
  7. lower hull = [(0,0),(2,0),(2,2)]

upper hull (reverse করে একইভাবে) = [(2,2),(0,2),(0,0)]। জুড়ে (endpoint বাদ দিয়ে): [(0,0),(2,0),(2,2),(0,2)] — কেন্দ্রের (1,1) বাদ পড়ল ✓।

12. Python solution

def orientation(a, b, c):
    """+1 = CCW, -1 = CW, 0 = collinear (116 থেকে)।"""
    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 convex_hull(points):
    """Andrew's monotone chain — CCW ক্রমে hull-এর vertex list।
    collinear point hull-এ রাখা হয় না; n <= 2 আলাদা handle।"""
    pts = sorted(set(points))          # x, tie-তে y; duplicate বাদ
    if len(pts) <= 2:
        return pts

    def build(seq):
        chain = []
        for p in seq:
            # বাঁ-বাঁক (CCW) না হলে আগেরটা pop
            while len(chain) >= 2 and orientation(chain[-2], chain[-1], p) <= 0:
                chain.pop()
            chain.append(p)
        return chain

    lower = build(pts)                 # বাঁ -> ডান
    upper = build(pts[::-1])           # ডান -> বাঁ
    # শেষ point প্রতিটা half-এ পরের half-এর শুরু, তাই বাদ
    return lower[:-1] + upper[:-1]


# --- ছোট test গুলো (সব pass করা উচিত) ---
sq = convex_hull([(0, 0), (2, 0), (2, 2), (0, 2), (1, 1)])
assert set(sq) == {(0, 0), (2, 0), (2, 2), (0, 2)}     # কেন্দ্র বাদ
assert len(sq) == 4

# সব collinear -> শুধু দুই প্রান্ত
line = convex_hull([(0, 0), (1, 1), (2, 2), (3, 3)])
assert set(line) == {(0, 0), (3, 3)}

# n <= 2
assert convex_hull([(0, 0), (2, 0)]) == [(0, 0), (2, 0)]
assert convex_hull([(5, 5)]) == [(5, 5)]

# ভেতরের point বাদ
h = convex_hull([(0, 0), (3, 1), (1, 4), (4, 4), (2, 2)])
assert (2, 2) not in set(h)            # ভেতরের point hull-এ নেই
assert (0, 0) in set(h) and (4, 4) in set(h)

# duplicate point নিরাপদে handle
d = convex_hull([(0, 0), (0, 0), (2, 0), (2, 2), (0, 2)])
assert set(d) == {(0, 0), (2, 0), (2, 2), (0, 2)}

# hull সবসময় CCW: signed area ধনাত্মক হওয়া উচিত
def signed_area2(poly):
    s = 0
    for i in range(len(poly)):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % len(poly)]
        s += x1 * y2 - x2 * y1
    return s
assert signed_area2(sq) > 0            # CCW orientation

print(sorted(sq))                      # বর্গের চার কোণা
print(convex_hull([(0, 0), (1, 1), (2, 2)]))   # [(0, 0), (2, 2)]
print("সব test pass!")

13. Line-by-line explanation

    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts

set দিয়ে duplicate বাদ, sorted করে x (tie-তে y) ক্রমে সাজাই — এটাই monotone chain-এর ভিত্তি। 2 বা কম point হলে আলাদা কিছু করার নেই, তারাই hull।

    def build(seq):
        chain = []
        for p in seq:
            while len(chain) >= 2 and orientation(chain[-2], chain[-1], p) <= 0:
                chain.pop()
            chain.append(p)
        return chain

এটাই হৃদয়। প্রতিটা নতুন point p-র জন্য: যতক্ষণ chain-এ অন্তত দুটো point আছে আর শেষ দুটো + p মিলে CCW নয় (<= 0 মানে CW বা collinear), ততক্ষণ শেষ point pop — কারণ সে hull-এর ভেতরে পড়ে গেছে। তারপর p যোগ।

    lower = build(pts)
    upper = build(pts[::-1])
    return lower[:-1] + upper[:-1]

বাঁ-থেকে-ডান হেঁটে lower hull, ডান-থেকে-বাঁ (reverse) হেঁটে upper hull। জোড়ার সময় প্রতিটা half-এর শেষ point পরের half-এর শুরুর সাথে এক, তাই [:-1] দিয়ে দুবার গোনা এড়াই।

বাকি assert লাইনগুলো — কেন্দ্র-বাদ, collinear, n≤2, ভেতরের point, duplicate, আর hull-এর CCW orientation — সব edge case যাচাই করছে; সব মিললে শেষে সব test pass!।

14. Output walkthrough

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

[(0, 0), (0, 2), (2, 0), (2, 2)]
[(0, 0), (2, 2)]
সব test pass!

প্রথম লাইন: বর্গ + কেন্দ্রের input-এ hull-এর চার কোণা (sort করে ছাপা) — কেন্দ্রের (1,1) নেই। দ্বিতীয়: তিনটে collinear point-এর hull মানে শুধু দুই প্রান্ত (0,0) আর (2,2)। তার আগের সব assert (CCW orientation সহ) চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(n log n) — sort-টাই প্রধান খরচ (O(n log n)); এরপর প্রতিটা point একবার push আর একবার pop হয় (amortized), তাই hull গড়া O(n)। মোট O(n log n)।

16. Space complexity

O(n) — sorted list আর hull chain রাখতে point-সংখ্যার সমানুপাতিক জায়গা।

17. Common mistakes

  1. n ≤ 2 আর সব-collinear edge case ভুলে যাওয়া — আগে handle না করলে chain বা জোড় ভেঙে পড়ে; আলাদা করে দেখো।
  2. duplicate point না সরানো — set দিয়ে আগে duplicate বাদ না দিলে orientation 0-এ অদ্ভুত আচরণ; sort-এর আগেই dedupe।
  3. < 0 না <= 0 — collinear নিয়ে দ্বিধা — <= 0 মানে hull-এর ধারে থাকা collinear point বাদ; ধারের point রাখতে চাইলে < 0 (problem-এর সংজ্ঞা দেখো)।
  4. endpoint দুবার গোনা — lower + upper সরাসরি জুড়লে জোড়ার দুই point পুনরাবৃত্ত হয়; [:-1] করতে ভুলো না।
  5. screen coordinate-এ চিহ্ন উল্টো — y নিচে বাড়লে CCW/CW উল্টে যায়, তখন pop শর্তও উল্টাতে হয়; convention আগে ঠিক করো।

18. Harder problems that inherit this idea

  • CSES — Convex Hull (https://cses.fi/problemset/task/2195) — ঠিক এই monotone chain; সীমানার সব point সহ hull চাওয়া হতে পারে।
  • LeetCode — Erect the Fence (https://leetcode.com/problems/erect-the-fence/) — সব গাছ ঘিরে বেড়া; এখানে সীমানার collinear point-ও রাখতে হয় (< বনাম <=-এর সুন্দর উদাহরণ)।
  • 124 (Pick's Theorem Intro) — এই repo-রই পরের ধাপ; hull/polygon-এর area থেকে ভেতরের lattice point গোনা।

19. Pattern learned

Convex hull via monotone chain — sort করো, বাঁ-থেকে-ডান (ও উল্টো) হেঁটে orientation দিয়ে "ভুল বাঁকে pop"; lower + upper জুড়ে hull, পুরোটা O(n log n) আর integer। বড় শিক্ষা: sort + stack + "শেষ বাঁক ঠিক দিকে?" — এই কাঠামো cross product-এর সাথে মিলে hull দেয়, আর একই কাঠামো monotonic-stack problem-এর হাড়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "convex hull = sort + monotone chain; প্রতিটা নতুন point-এ শেষ দুটোর সাথে orientation দেখো — CCW না হলে আগেরটা pop। lower + upper জুড়ো ([:-1]), O(n log n), integer। edge case: n≤2, সব collinear, duplicate — আগে সারো।"

পরের ধাপ → 121 — Manhattan Distance Tricks (45° rotation-এর CP-মশলা)। শিকড় → 116 — Orientation of Three Points। সম্পর্কিত → 124 — Pick's Theorem 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" লেখো।