Problem link ও উৎস
- **Original source:** CP-Algorithms — Convex Hull (Andrew's monotone chain)
- **Platform:** CP-Algorithms —
, CSES Convex Hull —
- **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 চিহ্নই বলে)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো point দেওয়া (একটা list of `(x, y)`)। বলতে হবে এদের সবাইকে ঘিরে রাখা সবচেয়ে ছোট **উত্তল (convex) বহুভুজ**-এর কোণাগুলো (vertices) কী কী।
"উত্তল" মানে — বহুভুজটার কোনো খাঁজ নেই, সব কোণ বাইরের দিকে ফোলা। আর "সবচেয়ে ছোট" মানে — এমন বহুভুজ যেটা সব point ভেতরে (বা সীমানায়) রাখে কিন্তু একটুও বেশি জায়গা নেয় না। বাকি ভেতরের point গুলো hull-এ থাকে না; শুধু একদম বাইরের point গুলোই কোণা হয়।
### Input ও output {#6-example-input-and-output}
```text
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 ভেঙে পড়ে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা কাঠের তক্তায় এলোমেলো কতগুলো পেরেক পোঁতা। তুমি একটা বড় রবার ব্যান্ড নিয়ে সবগুলো পেরেকের চারপাশে টেনে ধরে ছেড়ে দিলে। রবার ব্যান্ডটা ভেতরের দিকে যতটা পারে গুটিয়ে আসবে, কিন্তু একদম বাইরের পেরেকগুলোতে আটকে যাবে — আর যে আকার নেবে সেটাই **convex hull**।
ভেতরের পেরেকগুলো? রবার তাদের ছোঁয়েও না — তারা hull-এর অংশ নয়। monotone chain আসলে এই গুটিয়ে আসাটাই অনুকরণ করে: একটা একটা পেরেক ধরে এগোয়, আর যখন দেখে কোনো পেরেক ভেতরে পড়ে গেছে (রবার সেখানে আটকাবে না, "ভুল দিকে বাঁক"), তখন তাকে বাদ (pop) দেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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।)
### ভেতরের অঙ্ক {#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 নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
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।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
প্রতিটা জোড়ার জন্য বাকি সব point দেখা মানে তিন স্তরের loop:
```text
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:
```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 থাকে না।
### ভাবনার পরিবর্তন {#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-এর সাথে মিলেছে।
### ছবিতে বোঝা {#5-visual-explanation}
ভেতরের point গুলো বাদ পড়ে, শুধু বাইরের খোলস থাকে:
```text
সব 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-এ ধাপে ধাপে {#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) বাদ পড়ল ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#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!`।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 আগে ঠিক করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Convex Hull** (