কনটেন্টে যান

120 — Convex Hull Intro

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

Problem link ও উৎস

  • 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 চিহ্নই বলে)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

Input ও 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 ভেঙে পড়ে।

চেনা উদাহরণে বোঝা

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

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের অঙ্ক

মূল 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 নেই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

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

কোথায় বেশি কাজ হতে পারে

প্রতিটা জোড়ার জন্য বাকি সব 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 দিয়ে এই পুনরাবৃত্তি কাটিয়ে দেয়।

আরও ভালোভাবে ভাবা

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

Python
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 থাকে না।

ভাবনার পরিবর্তন

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

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

ছবিতে বোঝা

ভেতরের 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-এর চিহ্ন বলে দেয়।

ছোট input-এ ধাপে ধাপে

চলো [(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) বাদ পড়ল ✓।

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

উদাহরণ
    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!।

Output মিলিয়ে দেখা

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

উদাহরণ
[(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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  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 আগে ঠিক করো।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

  • 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 গোনা।

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।