124 — Pick's Theorem Intro¶
এই problem-টা geometry-র সবচেয়ে সুন্দর সূত্রগুলোর একটা — Pick's theorem। একটা বহুভুজের কোণাগুলো যদি সব গ্রিড-বিন্দুতে (lattice points) থাকে, তাহলে তার ক্ষেত্রফল, ভেতরের বিন্দু সংখ্যা আর ধারের বিন্দু সংখ্যা — তিনটে একটা আশ্চর্য সরল সমীকরণে বাঁধা:
A = I + B/2 − 1। এই এক সূত্র দিয়ে "ভেতরে কতগুলো গ্রিড-বিন্দু" — যা গুনতে গেলে কষ্টকর — তা তাৎক্ষণিক বের হয়। ছবি না এঁকে এই note বোঝা যাবে না, তাই গ্রিডগুলো মন দিয়ে দেখো।
Problem link ও উৎস
- Original source: CP-Algorithms — Pick's Theorem
- Platform: CP-Algorithms — https://cp-algorithms.com/geometry/picks-theorem.html
- Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- Difficulty: Hard
- Pattern: lattice counting (গ্রিড-বিন্দু গণনা ↔ ক্ষেত্রফল)
- Basic idea inherited from: 115 — Area of Triangle
প্রশ্ন ও উদাহরণ¶
সহজ করে প্রশ্ন¶
একটা বহুভুজ (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¶
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-এর ভুল এড়ানো যায়।
চেনা উদাহরণে বোঝা¶
ভাবো একটা পেরেক-বোর্ড (geoboard) — সমান ব্যবধানে পেরেক বসানো একটা কাঠের তক্তা, যেমন স্কুলে জ্যামিতি শেখাতে ব্যবহার হয়। তুমি একটা রাবার ব্যান্ড কয়েকটা পেরেকে আটকে একটা বহুভুজ বানালে। এখন তুমি জানতে চাও — এই রাবার-বহুভুজের ভেতরে কতগুলো পেরেক আটকা পড়ল?
একটা একটা করে ভেতরের পেরেক গোনা ক্লান্তিকর, আর বড় বহুভুজে ভুল হওয়া সহজ। Pick's theorem একটা শর্টকাট দেয়: তুমি শুধু (১) বহুভুজের ক্ষেত্রফল আর (২) রাবার ব্যান্ড যত পেরেক ছুঁয়ে গেছে (ধারের পেরেক) — এই দুটো জানলেই, ভেতরের পেরেক সংখ্যা এক সূত্রে বেরিয়ে আসে। যেন কেউ তোমাকে বলল — "ঘরের মেঝের আয়তন আর দেয়াল ঘেঁষা টাইলের সংখ্যা বলো, আমি বলে দিচ্ছি মাঝখানে কটা টাইল আছে।" গোনার কষ্ট নেই, শুধু একটা সরল হিসাব।
ভিত্তির ধারণা¶
আগের কোন ধারণাটি লাগবে¶
এটা সরাসরি দাঁড়িয়ে আছে 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-এর ভিত।
ভেতরের অঙ্ক¶
মূল সূত্র 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 (ডান পাশ সবসময় জোড়, তাই নিঃশেষে ভাগ যায়)।
ধাপে ধাপে সমাধান¶
প্রথম সরল উপায়¶
I (ভেতরের বিন্দু) সরাসরি গুনতে — bounding box-এর প্রতিটা গ্রিড-বিন্দু ধরে দেখো সেটা বহুভুজের কঠোরভাবে ভেতরে কিনা (ray casting দিয়ে, আর ধারে থাকলে বাদ):
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। ছোট বহুভুজে চমৎকার।
কোথায় বেশি কাজ হতে পারে¶
খরচ bounding box-এর আকারের সমানুপাতিক — (width × height) গ্রিড-বিন্দু, প্রতিটার জন্য O(কোণা সংখ্যা) ray casting। coordinate বড় হলে (যেমন 10⁹) bounding box বিশাল, সম্পূর্ণ অসম্ভব।
coordinate 10^6 পর্যন্ত হলে (bounding box ~10^6 × 10^6):
brute (প্রতি গ্রিড-বিন্দু): ~10^12 বিন্দু × কোণা (অসম্ভব)
Pick + shoelace + gcd : O(কোণা সংখ্যা) (তাৎক্ষণিক)
মূল অপচয় — আমরা প্রতিটা সম্ভাব্য ভেতরের বিন্দু আলাদা করে যাচাই করছি, যেখানে Pick's theorem ক্ষেত্রফল আর ধারের গণনা থেকে I এক সূত্রে দিয়ে দেয়। আর ক্ষেত্রফল ও ধার দুটোই কোণা-সংখ্যার সমানুপাতে (bounding box নয়) হিসাব হয়, তাই coordinate যত বড়ই হোক দ্রুত।
আরও ভালোভাবে ভাবা¶
মূল insight — I গুনতে গ্রিড চষার দরকার নেই; shoelace দিয়ে 2A, gcd দিয়ে B, তারপর Pick উল্টে I:
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 সবসময় জোড়।
ভাবনার পরিবর্তন¶
আসল "আহা!" — ভেতরের গ্রিড-বিন্দু আলাদা করে গোনার দরকার নেই; ক্ষেত্রফল আর ধারের বিন্দুই ভেতরের সংখ্যা বলে দেয় (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 ত্রয়ী মাথায় আসুক।
ছবিতে বোঝা¶
ত্রিভুজ (0,0), (4,0), (0,4) — interior (·), boundary (#), vertex (V):
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:
ধার (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:
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-এ ধাপে ধাপে¶
বহুভুজ = ত্রিভুজ (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 গণনার সাথেও।
কোড ও ব্যাখ্যা¶
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!")
কোডের প্রতিটি অংশ¶
shoelace formula (115-এর) — পরপর কোণার জোড়ায় cross product যোগ। ফল 2A (দ্বিগুণ ক্ষেত্রফল), সবসময় পূর্ণসংখ্যা, তাই float-এর ঝামেলা নেই। abs নেওয়ায় কোণার ক্রম (CW/CCW) যাই হোক ঠিক মান।
প্রতিটা ধারের lattice point অবদান। একটা সরলরেখাংশে গ্রিড-বিন্দু সমান ব্যবধানে বসে, আর সেই ব্যবধান-সংখ্যা = gcd(|Δx|, |Δy|)। সব ধার যোগ করলে প্রতিটা কোণা ঠিক একবার গোনা হয় (একটার শেষ = পরেরটার শুরু), তাই মোট B।
Pick উল্টানো: A = I + B/2 − 1 থেকে 2A = 2I + B − 2, তাই I = (2A − B + 2) / 2। 2A − B + 2 সবসময় জোড় (Pick-এর গ্যারান্টি), তাই integer // নিরাপদ — কোনো rounding ভুল নেই।
সোজা দিক — I ও B জানা থাকলে 2A বের করা (একই সূত্র উল্টো)। float এড়াতে দ্বিগুণ ক্ষেত্রফল ফেরায়।
cross-check অংশে 1500টা random (অ-অবক্ষয়ী) ত্রিভুজে Pick-পথ আর গ্রিড-চষা brute মিলিয়ে দেখা — সব মিললে সব test pass!।
Output মিলিয়ে দেখা¶
চালালে যা ছাপবে:
প্রথম লাইন: ত্রিভুজ (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 সূত্র প্রতিটা কেসে গ্রিড-চষার সাথে মিলেছে।
খরচ ও সাধারণ ভুল¶
সময়¶
O(n) — n = কোণার সংখ্যা। shoelace, boundary (gcd যোগফল) — দুটোই কোণা ধরে একবার ঘোরে; প্রতি gcd O(log(coordinate))। তাই মোট O(n log(max coordinate)), কার্যত O(n)। coordinate কত বড় তাতে bounding box-এর মতো বিস্ফোরণ নেই (brute-এর তুলনায় বিশাল লাভ)।
অতিরিক্ত জায়গা¶
O(1) বাড়তি — input বহুভুজ ছাড়া শুধু কয়েকটা accumulator (s, b)। কোনো গ্রিড, set বা array লাগে না। (brute reference bounding box চষে কিন্তু গণনা O(1) জায়গায়; আসল Pick-সমাধান নিজেও O(1) বাড়তি।)
যে ভুলগুলো এড়াতে হবে¶
- float-এ ক্ষেত্রফল রাখা —
Aভগ্নাংশ হলে rounding ভুল; সবসময়2A(integer) দিয়ে কাজ করো, শেষেI = (2A − B + 2)//2। B-তে gcd-এর−1ভুলভাবে প্রয়োগ — প্রতি ধারে ভেতরের বিন্দুgcd − 1, কিন্তু সব ধার যোগ করলে কোণাগুলো ঠিক একবার গোনা হয়ে মোটB = Σ gcd; ধরে ধরে−1করলে কোণা কম গোনা হবে।- shoelace-এ
absভুলে যাওয়া — কোণা CW ক্রমে দিলে2Aঋণাত্মক আসে;absনা নিলেIভুল। - non-lattice কোণায় Pick লাগানো — Pick's theorem শুধু lattice (পূর্ণসংখ্যা coordinate) কোণায় খাটে; ভগ্নাংশ কোণায় নয়।
- self-intersecting বহুভুজ — Pick সরল (non-self-intersecting) বহুভুজ ধরে নেয়; ধার কাটাকাটি করলে সূত্র ভাঙে।
শেখা ও পরের অনুশীলন¶
এই ধারণার পরের অনুশীলন¶
- CP-Algorithms — Pick's Theorem (https://cp-algorithms.com/geometry/picks-theorem.html) — মূল তত্ত্ব ও আরও প্রয়োগ; এই note-এর উৎস।
- CSES — Polygon Lattice Points (https://cses.fi/problemset/task/2191) — সরাসরি Pick প্রয়োগ: ধারের ও ভেতরের বিন্দু গোনা।
- CSES — Polygon Area (https://cses.fi/problemset/task/2191) ও shoelace-নির্ভর problem — ক্ষেত্রফল ভিত্তি যেখানে Pick-এর সাথে মেলে।
কৌশলটি মনে রাখুন¶
Pick's theorem (lattice counting via area + boundary) — lattice polygon-এ A = I + B/2 − 1; 2A shoelace-এ, B = Σ gcd(|Δx|, |Δy|), তারপর I = (2A − B + 2)//2 — সব integer। বড় শিক্ষা: ভেতরের গ্রিড-বিন্দু সরাসরি গোনার দরকার নেই — ক্ষেত্রফল আর ধারের বিন্দুই তা বলে দেয়; আর float এড়াতে সবসময় 2A দিয়ে হিসাব করো (2A, B, I সব পূর্ণসংখ্যা)।
নিজেকে যাচাই করুন¶
ভবিষ্যতের আমাকে এক লাইনে: "Pick's theorem = A = I + B/2 − 1; 2A shoelace, B = Σ gcd(|Δx|,|Δy|), I = (2A − B + 2)//2 (সব integer, float নয়)। Signal: 'lattice polygon-এ ভেতরের/ধারের বিন্দু বা ক্ষেত্রফল' দেখলেই Pick + shoelace + gcd ত্রয়ী মনে পড়ুক।"
পরের ধাপ → এই level সম্পূর্ণ; পরের level → ../../10-advanced-number-theory/problems/README.md। ভিত্তি → 115 — Area of Triangle (shoelace-এর শিকড়)। সম্পর্কিত → 114 — Slope and Collinearity (gcd-চিন্তা)।
ফিরে দেখা: এই level-এর map → ../README.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" লেখো।