Problem link ও উৎস
- **Original source:** CP-Algorithms — Pick's Theorem
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Hard
- **Pattern:** lattice counting (গ্রিড-বিন্দু গণনা ↔ ক্ষেত্রফল)
- **Basic idea inherited from:** 115 — Area of Triangle
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা বহুভুজ (polygon) দেওয়া যার প্রতিটা কোণা (vertex) একটা **lattice point** — অর্থাৎ পূর্ণসংখ্যা coordinate-এর গ্রিড-বিন্দু (যেমন (0,0), (4,0), (3,2))। তিনটে রাশি নিয়ে আমরা খেলব:
- **`A`** = বহুভুজের ক্ষেত্রফল (area)।
- **`I`** = বহুভুজের **ভেতরে** থাকা lattice point-এর সংখ্যা (interior)।
- **`B`** = বহুভুজের **ধারে/সীমানায়** থাকা lattice point-এর সংখ্যা (boundary)।
**Pick's theorem** বলে এই তিনটে সবসময় এক সম্পর্কে বাঁধা: **`A = I + B/2 − 1`**।
এই সূত্র থেকে যেকোনো একটা রাশি বাকি দুটো দিয়ে বের করা যায়। সবচেয়ে কাজের প্রয়োগ — `I` (ভেতরের বিন্দু) বের করা, যা সরাসরি গুনতে গেলে কষ্ট: সূত্র উল্টে `I = A − B/2 + 1`। উদাহরণ: কোণা (0,0), (4,0), (0,4)-এর ত্রিভুজে `A = 8`, `B = 12`, তাই `I = 8 − 6 + 1 = 3` (ভেতরে ঠিক 3টা গ্রিড-বিন্দু)।
### Input ও output {#6-example-input-and-output}
```text
polygon (lattice কোণা) A B I যাচাই A=I+B/2-1
-----------------------------------------------------------
(0,0),(4,0),(0,4) 8 12 3 3+6-1 = 8 ✓
(0,0),(1,0),(0,1) 0.5 3 0 0+1.5-1 = 0.5 ✓ (খালি ত্রিভুজ)
(0,0),(3,0),(3,3),(0,3) 9 12 4 4+6-1 = 9 ✓
(0,0),(4,0),(4,2),(0,2) 8 12 3 3+6-1 = 8 ✓
(0,0),(5,0),(3,4) 10 8 7 7+4-1 = 10 ✓
```
মূল edge case: **সবচেয়ে ছোট lattice ত্রিভুজ** (0,0),(1,0),(0,1) — A = 0.5, I = 0, B = 3 (কোনো ভেতরের বিন্দু নেই, এটাই Pick-এর সীমা ক্ষেত্রে)। আরেকটা সূক্ষ্মতা — **A ভগ্নাংশ হতে পারে** (½-এর গুণিতক), কিন্তু `2A`, `B`, `I` সবসময় পূর্ণসংখ্যা; তাই হিসাব `2A` দিয়ে করলে float-এর ভুল এড়ানো যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পেরেক-বোর্ড (geoboard) — সমান ব্যবধানে পেরেক বসানো একটা কাঠের তক্তা, যেমন স্কুলে জ্যামিতি শেখাতে ব্যবহার হয়। তুমি একটা রাবার ব্যান্ড কয়েকটা পেরেকে আটকে একটা বহুভুজ বানালে। এখন তুমি জানতে চাও — এই রাবার-বহুভুজের ভেতরে কতগুলো পেরেক আটকা পড়ল?
একটা একটা করে ভেতরের পেরেক গোনা ক্লান্তিকর, আর বড় বহুভুজে ভুল হওয়া সহজ। Pick's theorem একটা শর্টকাট দেয়: তুমি শুধু (১) বহুভুজের ক্ষেত্রফল আর (২) রাবার ব্যান্ড যত পেরেক ছুঁয়ে গেছে (ধারের পেরেক) — এই দুটো জানলেই, ভেতরের পেরেক সংখ্যা এক সূত্রে বেরিয়ে আসে। যেন কেউ তোমাকে বলল — "ঘরের মেঝের আয়তন আর দেয়াল ঘেঁষা টাইলের সংখ্যা বলো, আমি বলে দিচ্ছি মাঝখানে কটা টাইল আছে।" গোনার কষ্ট নেই, শুধু একটা সরল হিসাব।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি দাঁড়িয়ে আছে **115 — Area of Triangle**-এর উপর, যেখানে তুমি **shoelace formula** শিখেছিলে — coordinate থেকে ক্ষেত্রফল বের করা, আর `2A`-কে integer রাখার কৌশল। Pick's theorem সেই ক্ষেত্রফলকেই একটা নতুন কাজে লাগায়: ক্ষেত্রফল ↔ গ্রিড-বিন্দু গণনার সেতু।
নতুন যেটা যোগ হলো — gcd দিয়ে ধারের lattice point গোনা (114-এর slope/cross-multiply চিন্তার আত্মীয়, যেখানে gcd দিয়ে দিক সরল করা হয়), আর তিন রাশির বীজগণিতীয় সম্পর্ক। তাই বলা যায় এই problem = 115-এর shoelace (ক্ষেত্রফল) + একটা gcd-গণনা (ধার) + Pick-এর সমীকরণ। আটকে গেলে 115-এ ফিরে shoelace ঝালাই করো — এটাই এই note-এর ভিত।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল সূত্র **`A = I + B/2 − 1`** — lattice polygon-এর ক্ষেত্রফল ও গ্রিড-বিন্দু সংখ্যার সেতু। একে কাজে লাগাতে দুটো জিনিস integer-এ হিসাব করতে জানতে হয়:
**(ক) ক্ষেত্রফল — shoelace formula** (115-এ শেখা): `2A = |Σ (x_i · y_{i+1} − x_{i+1} · y_i)|`। লক্ষ করো আমরা `2A` (দ্বিগুণ ক্ষেত্রফল) রাখি — সেটা সবসময় পূর্ণসংখ্যা, তাই float এড়ানো যায়।
**(খ) ধারের বিন্দু — `B`**: প্রতিটা ধার `(x1,y1)→(x2,y2)`-এর উপর (প্রান্ত বাদে) lattice point সংখ্যা = `gcd(|x2−x1|, |y2−y1|) − 1`, আর প্রতিটা কোণা একবার গোনা — সব মিলিয়ে `B = Σ gcd(|Δx|, |Δy|)`। (কেন gcd? একটা সরলরেখাংশে গ্রিড-বিন্দুগুলো সমান ব্যবধানে বসে, আর সেই ব্যবধান-সংখ্যা = gcd।)
দুটো মিলিয়ে `I` বের করতে সূত্র উল্টাই — float ছাড়া পরিষ্কার integer-এ: `A = I + B/2 − 1` ⟹ `2A = 2I + B − 2` ⟹ **`I = (2A − B + 2) / 2`** (ডান পাশ সবসময় জোড়, তাই নিঃশেষে ভাগ যায়)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
`I` (ভেতরের বিন্দু) সরাসরি গুনতে — bounding box-এর প্রতিটা গ্রিড-বিন্দু ধরে দেখো সেটা বহুভুজের কঠোরভাবে ভেতরে কিনা (ray casting দিয়ে, আর ধারে থাকলে বাদ):
```python
def interior_brute(pts):
xs = [p[0] for p in pts]
ys = [p[1] for p in pts]
def on_boundary(px, py):
n = len(pts)
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
cross = (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1)
if cross == 0 and min(x1, x2) <= px <= max(x1, x2) and min(y1, y2) <= py <= max(y1, y2):
return True
return False
def inside(px, py): # ray casting (strict interior)
if on_boundary(px, py):
return False
cnt = 0
n = len(pts)
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
if (y1 > py) != (y2 > py):
xint = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
if px < xint:
cnt += 1
return cnt % 2 == 1
return sum(inside(px, py)
for px in range(min(xs), max(xs) + 1)
for py in range(min(ys), max(ys) + 1))
```
এটা প্রতিটা গ্রিড-বিন্দু পরীক্ষা করে, তাই নিশ্চিত ঠিক — asserts-এ এটাই reference। ছোট বহুভুজে চমৎকার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
খরচ bounding box-এর আকারের সমানুপাতিক — `(width × height)` গ্রিড-বিন্দু, প্রতিটার জন্য O(কোণা সংখ্যা) ray casting। coordinate বড় হলে (যেমন 10⁹) bounding box বিশাল, সম্পূর্ণ অসম্ভব।
```text
coordinate 10^6 পর্যন্ত হলে (bounding box ~10^6 × 10^6):
brute (প্রতি গ্রিড-বিন্দু): ~10^12 বিন্দু × কোণা (অসম্ভব)
Pick + shoelace + gcd : O(কোণা সংখ্যা) (তাৎক্ষণিক)
```
মূল অপচয় — আমরা প্রতিটা সম্ভাব্য ভেতরের বিন্দু আলাদা করে যাচাই করছি, যেখানে Pick's theorem ক্ষেত্রফল আর ধারের গণনা থেকে `I` এক সূত্রে দিয়ে দেয়। আর ক্ষেত্রফল ও ধার দুটোই কোণা-সংখ্যার সমানুপাতে (bounding box নয়) হিসাব হয়, তাই coordinate যত বড়ই হোক দ্রুত।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — `I` গুনতে গ্রিড চষার দরকার নেই; shoelace দিয়ে `2A`, gcd দিয়ে `B`, তারপর Pick উল্টে `I`:
```python
from math import gcd
def poly_area2(pts): # 2A (পূর্ণসংখ্যা)
n = len(pts); s = 0
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
s += x1 * y2 - x2 * y1
return abs(s)
def boundary_points(pts): # B = Σ gcd(|Δx|, |Δy|)
n = len(pts); b = 0
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
b += gcd(abs(x2 - x1), abs(y2 - y1))
return b
def interior_points(pts): # Pick: I = (2A - B + 2) / 2
return (poly_area2(pts) - boundary_points(pts) + 2) // 2
```
তিনটে function-ই কোণা ধরে একবার ঘোরে — O(n) (n = কোণা সংখ্যা)। float একদম নেই; সব integer, তাই নিখুঁত। `//` নিরাপদ কারণ `2A − B + 2` সবসময় জোড়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **ভেতরের গ্রিড-বিন্দু আলাদা করে গোনার দরকার নেই; ক্ষেত্রফল আর ধারের বিন্দুই ভেতরের সংখ্যা বলে দেয়** (Pick: `I = A − B/2 + 1`)। কঠিন গণনা (interior) সহজ গণনায় (area + boundary) রূপান্তরিত।
দ্বিতীয় tweak — **float এড়াও, `2A`-তে কাজ করো।** ক্ষেত্রফল ভগ্নাংশ হতে পারে, কিন্তু `2A`, `B`, `I` সব পূর্ণসংখ্যা; তাই Pick-কে `2A = 2I + B − 2`-তে লিখে `I = (2A − B + 2) / 2` — কোনো rounding ঝুঁকি নেই। আর তৃতীয় — **ধারের বিন্দু = gcd**: সরলরেখাংশে গ্রিড-বিন্দু সমান ব্যবধানে, সংখ্যা gcd(|Δx|,|Δy|)। "lattice polygon + ভেতরের/ধারের বিন্দু বা ক্ষেত্রফল" দেখলেই Pick + shoelace + gcd ত্রয়ী মাথায় আসুক।
### ছবিতে বোঝা {#5-visual-explanation}
ত্রিভুজ (0,0), (4,0), (0,4) — interior (·), boundary (#), vertex (V):
```text
y=4 V
y=3 # ·
y=2 # · · I = 3 (ভেতরের · বিন্দু: (1,1),(2,1),(1,2))
y=1 # · · · B = 12 (# ও V, ধারের সব বিন্দু)
y=0 V # # # V A = 8 (shoelace)
x=0 1 2 3 4
যাচাই: A = I + B/2 - 1 = 3 + 12/2 - 1 = 3 + 6 - 1 = 8 ✓
```
`B` কীভাবে gcd দিয়ে — প্রতিটা ধারের ভেতরের বিন্দু `gcd(|Δx|, |Δy|) − 1`:
```text
ধার (0,0)->(4,0): gcd(4,0)=4 -> ধারের 4টা ব্যবধান (বিন্দু: (1,0),(2,0),(3,0) + প্রান্ত)
ধার (4,0)->(0,4): gcd(4,4)=4 -> কর্ণে 4টা ব্যবধান (বিন্দু: (3,1),(2,2),(1,3) + প্রান্ত)
ধার (0,4)->(0,0): gcd(0,4)=4 -> খাড়া 4টা ব্যবধান
B = gcd যোগফল = 4 + 4 + 4 = 12 (প্রতিটা কোণা ঠিক একবার গোনা হয়)
```
shoelace দিয়ে `2A`:
```text
2A = |x0·y1 - x1·y0 + x1·y2 - x2·y1 + x2·y0 - x0·y2|
= |0·0 - 4·0 + 4·4 - 0·0 + 0·0 - 0·4|
= |16| = 16 -> A = 8
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
বহুভুজ = ত্রিভুজ (0,0), (4,0), (0,4)। `I` বের করি:
**ধাপ 1 — `2A` (shoelace):** কোণা ক্রমে নিয়ে `Σ (x_i·y_{i+1} − x_{i+1}·y_i)`:
- (0,0)→(4,0): `0·0 − 4·0` = 0
- (4,0)→(0,4): `4·4 − 0·0` = 16
- (0,4)→(0,0): `0·0 − 0·4` = 0
- যোগ = 16, `2A = |16|` = 16 (তাই A = 8)।
**ধাপ 2 — `B` (gcd যোগফল):**
- (0,0)→(4,0): `gcd(|4|, |0|)` = gcd(4,0) = 4
- (4,0)→(0,4): `gcd(|−4|, |4|)` = gcd(4,4) = 4
- (0,4)→(0,0): `gcd(|0|, |−4|)` = gcd(0,4) = 4
- `B` = 4 + 4 + 4 = 12।
**ধাপ 3 — Pick উল্টে `I`:** `I = (2A − B + 2) / 2` = `(16 − 12 + 2) / 2` = `6 / 2` = **3**।
মানে ভেতরে ঠিক 3টা গ্রিড-বিন্দু: (1,1), (2,1), (1,2) — section 5-এর ছবির সাথে মেলে, আর brute force গণনার সাথেও।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import gcd
def poly_area2(pts):
"""বহুভুজের দ্বিগুণ ক্ষেত্রফল |2A| (shoelace, পূর্ণসংখ্যা)। O(n)।"""
n = len(pts)
s = 0
for i in range(n):
x1, y1 = pts[i]
x2, y2 = pts[(i + 1) % n]
s += x1 * y2 - x2 * y1
return abs(s)
def boundary_points(pts):
"""ধারে থাকা lattice point সংখ্যা B = Σ gcd(|Δx|, |Δy|)। O(n)।"""
n = len(pts)
b = 0
for i in range(n):
x1, y1 = pts[i]
x2, y2 = pts[(i + 1) % n]
b += gcd(abs(x2 - x1), abs(y2 - y1))
return b
def interior_points(pts):
"""ভেতরের lattice point I, Pick উল্টে: I = (2A - B + 2) // 2। O(n)।"""
return (poly_area2(pts) - boundary_points(pts) + 2) // 2
def pick_area_times2(I, B):
"""Pick সোজা দিকে: 2A = 2I + B - 2 (float এড়িয়ে দ্বিগুণ ক্ষেত্রফল)।"""
return 2 * I + B - 2
def interior_brute(pts):
"""প্রতিটা গ্রিড-বিন্দু পরীক্ষা করে I — reference (ছোট বহুভুজ)।"""
xs = [p[0] for p in pts]
ys = [p[1] for p in pts]
n = len(pts)
def on_boundary(px, py):
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
cross = (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1)
if cross == 0 and min(x1, x2) <= px <= max(x1, x2) and min(y1, y2) <= py <= max(y1, y2):
return True
return False
def inside(px, py):
if on_boundary(px, py):
return False
cnt = 0
for i in range(n):
x1, y1 = pts[i]; x2, y2 = pts[(i + 1) % n]
if (y1 > py) != (y2 > py):
xint = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
if px < xint:
cnt += 1
return cnt % 2 == 1
return sum(inside(px, py)
for px in range(min(xs), max(xs) + 1)
for py in range(min(ys), max(ys) + 1))
# --- হাতে বাছা test ---
tri = [(0, 0), (4, 0), (0, 4)]
assert poly_area2(tri) == 16 # 2A = 16, A = 8
assert boundary_points(tri) == 12 # B = 12
assert interior_points(tri) == 3 # I = 3
unit = [(0, 0), (1, 0), (0, 1)]
assert poly_area2(unit) == 1 # 2A = 1, A = 0.5
assert boundary_points(unit) == 3
assert interior_points(unit) == 0 # খালি ত্রিভুজ
square = [(0, 0), (3, 0), (3, 3), (0, 3)]
assert poly_area2(square) == 18 # A = 9
assert boundary_points(square) == 12
assert interior_points(square) == 4
assert interior_points([(0, 0), (5, 0), (3, 4)]) == 7
# Pick সোজা দিক যাচাই: 2A = 2I + B - 2
assert pick_area_times2(3, 12) == 16 # ত্রিভুজ
assert pick_area_times2(4, 12) == 18 # বর্গ
# --- brute force-এর সাথে cross-check (random উত্তল ত্রিভুজ) ---
import random
random.seed(9)
checked = 0
while checked < 1500:
p = [(random.randint(-6, 6), random.randint(-6, 6)) for _ in range(3)]
if poly_area2(p) == 0: # collinear/অবক্ষয়ী — বাদ
continue
assert interior_points(p) == interior_brute(p), p
checked += 1
print(interior_points([(0, 0), (4, 0), (0, 4)])) # 3
print(interior_points([(0, 0), (3, 0), (3, 3), (0, 3)])) # 4
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
s += x1 * y2 - x2 * y1
...
return abs(s)
```
shoelace formula (115-এর) — পরপর কোণার জোড়ায় cross product যোগ। ফল `2A` (দ্বিগুণ ক্ষেত্রফল), সবসময় পূর্ণসংখ্যা, তাই float-এর ঝামেলা নেই। `abs` নেওয়ায় কোণার ক্রম (CW/CCW) যাই হোক ঠিক মান।
```text
b += gcd(abs(x2 - x1), abs(y2 - y1))
```
প্রতিটা ধারের lattice point অবদান। একটা সরলরেখাংশে গ্রিড-বিন্দু সমান ব্যবধানে বসে, আর সেই ব্যবধান-সংখ্যা = `gcd(|Δx|, |Δy|)`। সব ধার যোগ করলে প্রতিটা কোণা ঠিক একবার গোনা হয় (একটার শেষ = পরেরটার শুরু), তাই মোট `B`।
```text
return (poly_area2(pts) - boundary_points(pts) + 2) // 2
```
Pick উল্টানো: `A = I + B/2 − 1` থেকে `2A = 2I + B − 2`, তাই `I = (2A − B + 2) / 2`। `2A − B + 2` সবসময় জোড় (Pick-এর গ্যারান্টি), তাই integer `//` নিরাপদ — কোনো rounding ভুল নেই।
```text
def pick_area_times2(I, B): return 2 * I + B - 2
```
সোজা দিক — `I` ও `B` জানা থাকলে `2A` বের করা (একই সূত্র উল্টো)। float এড়াতে দ্বিগুণ ক্ষেত্রফল ফেরায়।
cross-check অংশে 1500টা random (অ-অবক্ষয়ী) ত্রিভুজে Pick-পথ আর গ্রিড-চষা brute মিলিয়ে দেখা — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
4
সব test pass!
```
প্রথম লাইন: ত্রিভুজ (0,0),(4,0),(0,4) → dry run-এ পাওয়া I = 3। দ্বিতীয়: বর্গ (0,0)–(3,3) → A = 9, B = 12, I = `(18 − 12 + 2)/2` = 4। তার আগের সব `assert` (shoelace, boundary, interior, Pick সোজা দিক + 1500টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — Pick সূত্র প্রতিটা কেসে গ্রিড-চষার সাথে মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — n = কোণার সংখ্যা। shoelace, boundary (gcd যোগফল) — দুটোই কোণা ধরে একবার ঘোরে; প্রতি gcd O(log(coordinate))। তাই মোট O(n log(max coordinate)), কার্যত O(n)। coordinate কত বড় তাতে bounding box-এর মতো বিস্ফোরণ নেই (brute-এর তুলনায় বিশাল লাভ)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** বাড়তি — input বহুভুজ ছাড়া শুধু কয়েকটা accumulator (`s`, `b`)। কোনো গ্রিড, set বা array লাগে না। (brute reference bounding box চষে কিন্তু গণনা O(1) জায়গায়; আসল Pick-সমাধান নিজেও O(1) বাড়তি।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **float-এ ক্ষেত্রফল রাখা** — `A` ভগ্নাংশ হলে rounding ভুল; সবসময় `2A` (integer) দিয়ে কাজ করো, শেষে `I = (2A − B + 2)//2`।
2. **`B`-তে gcd-এর `−1` ভুলভাবে প্রয়োগ** — *প্রতি ধারে* ভেতরের বিন্দু `gcd − 1`, কিন্তু সব ধার যোগ করলে কোণাগুলো ঠিক একবার গোনা হয়ে মোট `B = Σ gcd`; ধরে ধরে `−1` করলে কোণা কম গোনা হবে।
3. **shoelace-এ `abs` ভুলে যাওয়া** — কোণা CW ক্রমে দিলে `2A` ঋণাত্মক আসে; `abs` না নিলে `I` ভুল।
4. **non-lattice কোণায় Pick লাগানো** — Pick's theorem শুধু lattice (পূর্ণসংখ্যা coordinate) কোণায় খাটে; ভগ্নাংশ কোণায় নয়।
5. **self-intersecting বহুভুজ** — Pick সরল (non-self-intersecting) বহুভুজ ধরে নেয়; ধার কাটাকাটি করলে সূত্র ভাঙে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Pick's Theorem** (