Concept Notes — Geometry & Coordinate Math (এক অস্ত্রে অনেক যুদ্ধ)¶
এই note-এর মূল বার্তা: coordinate geometry-র 80% problem cross product নামের একটা ছোট সূত্রে নেমে আসে। সেটা একবার ভেতর থেকে বুঝলে orientation, area, intersection, convex hull — সব একই গল্পের অধ্যায়। আর পুরোটা integer-এ — float-এর ভয় ছাড়াই।
1. Point = ছোট vector — বিয়োগ মানে তীর¶
Point-কে Python-এ tuple ভাবো: p = (3, 4)। দুটো point বিয়োগ করলে পাও একটা vector — A থেকে B-র দিকে একটা তীর:
def sub(a, b): # b থেকে a-র দিকে তীর... না! a − b মানে b → a
return (a[0] - b[0], a[1] - b[1])
A, B = (1, 1), (4, 3)
AB = sub(B, A) # (3, 2): A থেকে B যেতে ডানে 3, উপরে 2
এই তীর-ভাবনাটাই সব কিছুর ভিত্তি: "তিনটা point কেমন সাজানো" প্রশ্নটা আসলে "দুটো তীর একে অপরের তুলনায় কোন দিকে বাঁকা" প্রশ্ন।
2. Squared distance — sqrt-কে বিদায়¶
দূরত্বের সূত্র √(dx² + dy²) — কিন্তু √ মানেই float। আর float তুলনা মানেই বিপদ। সুখবর: দূরত্ব তুলনা করতে sqrt লাগেই না, কারণ দুটো অঋণাত্মক সংখ্যায় a < b ⟺ a² < b²।
def dist2(a, b):
dx, dy = a[0] - b[0], a[1] - b[1]
return dx * dx + dy * dy # পুরোটা integer!
# কোন point টা origin-এর কাছে?
p, q = (3, 4), (5, 1)
print(dist2(p, (0, 0)), dist2(q, (0, 0))) # 25, 26 → p কাছে
আসল দূরত্ব 5 আর √26 ≈ 5.099 — তুলনার ফল একই, কিন্তু আমাদের হিসাবে এক ফোঁটাও float নেই। নিয়ম: শেষ উত্তরে দূরত্বের মান printing-এর আগ পর্যন্ত squared-এই থাকো।
3. Slope-এর বিপদ আর cross multiplication¶
তিনটা point collinear (এক লাইনে) কি না — স্কুলের পদ্ধতি: slope মিলিয়ে দেখো। কিন্তু:
Vertical line-এ এই formula ভেঙে পড়ে, আর float division-এ 1/3 আর 0.333... মেলে না। সমাধান: ভাগটা cross multiplication-এ বদলাও। (y2−y1)/(x2−x1) == (y3−y1)/(x3−x1) — দুই পাশে গুণ করে:
def collinear(a, b, c):
return (b[1] - a[1]) * (c[0] - a[0]) == (c[1] - a[1]) * (b[0] - a[0])
print(collinear((0, 0), (0, 5), (0, 9))) # True — vertical line, কোনো error নেই
print(collinear((0, 0), (1, 1), (2, 3))) # False
কোনো ভাগ নেই, কোনো float নেই, কোনো special case নেই। এই "ভাগকে গুণে বদলাও" কৌশলটা geometry-র সর্বত্র চলবে।
4. Cross product — এই level-এর হৃদপিণ্ড¶
দুটো vector u = (ux, uy) আর v = (vx, vy)-এর cross product:
এই একটা সংখ্যার দুটো অর্থ:
- |cross| = u আর v দিয়ে বানানো parallelogram-এর area (triangle-এর double area)
- sign বলে দেয় v vector-টা u-এর তুলনায় কোন দিকে বাঁকা
তিনটা point A, B, C-র জন্য orientation:
def orientation(a, b, c):
# AB vector-এর তুলনায় AC কোন দিকে?
val = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
if val > 0: return +1 # counter-clockwise (CCW) — বাঁয়ে বাঁক
if val < 0: return -1 # clockwise (CW) — ডানে বাঁক
return 0 # collinear
ছবিতে (standard math axes — y উপরে বাড়ে):
Mini dry run: A=(0,0), B=(4,0), C=(2,3) → val = 4·3 − 0·2 = 12 > 0 → CCW ✓ (C উপরে, মানে AB থেকে বাঁয়ে)। আর C=(2,−3) দিলে val = −12 → CW। সতর্কতা: screen coordinates-এ (y নিচে বাড়ে) sign উল্টে যায় — convention একবার ঠিক করে comment-এ লিখে রাখো।
5. Shoelace — area মানে cross product-এর যোগফল¶
Triangle A, B, C-এর area = |cross(AB, AC)| / 2। আর n-কোণা polygon-এ vertex গুলো ঘুরিয়ে cross product-এর যোগফল — এটাই shoelace (জুতার ফিতার মতো আড়াআড়ি গুণ):
def polygon_area2(pts): # doubled area, integer-এ থাকার জন্য
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 # আড়াআড়ি গুণ — এ জন্যই "shoelace"
return abs(s) # আসল area = s / 2
print(polygon_area2([(0, 0), (4, 0), (4, 3), (0, 3)])) # 24 → area 12 ✓
Dry run (4×3 rectangle): (0·0−4·0) + (4·3−4·0) + (4·3−0·3) + (0·0−0·0) = 0 + 12 + 12 + 0 = 24। abs দরকার কারণ CW ঘুরলে যোগফল negative — sign টা আসলে ঘোরার দিক বলে দেয়, এটাও কাজে লাগে!
6. Segment intersection — orientation-এর চার প্রশ্ন¶
Segment PQ আর RS কাটে কি না — line equation মেলানোর দরকার নেই। প্রশ্ন চারটা:
R আর S কি PQ-এর দুই পাশে? → orientation(P,Q,R) ≠ orientation(P,Q,S)
P আর Q কি RS-এর দুই পাশে? → orientation(R,S,P) ≠ orientation(R,S,Q)
দুটোই হ্যাঁ হলে কাটে। ছবিতে:
R R S
│ (PQ-এর উপরে) ╲ ╱ ← দুজনেই একই পাশে:
P───────┼───────Q P──────╳────Q কাটে না (প্রথম শর্ত fail)
│ (এখানে আসলে R,S দুটোই উপরে)
S (নিচে) → কাটে ✓
def segments_intersect(p, q, r, s):
o1, o2 = orientation(p, q, r), orientation(p, q, s)
o3, o4 = orientation(r, s, p), orientation(r, s, q)
if o1 != o2 and o3 != o4:
return True
# collinear special case: কোনো orientation 0 হলে দেখতে হয়
# endpoint টা অন্য segment-এর bounding box-এ পড়ে কি না
def on_seg(a, b, c): # c কি AB segment-এর উপর? (collinear ধরে)
return min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and \
min(a[1], b[1]) <= c[1] <= max(a[1], b[1])
if o1 == 0 and on_seg(p, q, r): return True
if o2 == 0 and on_seg(p, q, s): return True
if o3 == 0 and on_seg(r, s, p): return True
if o4 == 0 and on_seg(r, s, q): return True
return False
General case দুই লাইনের; বাকি সব collinear-এর special case — আর WA-র 90% আসে ওই special case ভুলে যাওয়া থেকেই।
7. Rectangle overlap — negation trick¶
Axis-aligned দুটো rectangle (প্রতিটা (x1, y1, x2, y2) — নিচ-বাঁ আর উপর-ডান কোণ) overlap করে কি? সরাসরি ভাবলে case-এর জঙ্গল। উল্টো প্রশ্নটা সহজ: কখন overlap করে না? — একটা পুরোপুরি অন্যটার বাঁয়ে / ডানে / উপরে / নিচে থাকলে:
আসলে এটা প্রতি axis-এ আলাদা 1D interval overlap check: x-interval গুলো overlap করে এবং y-interval গুলো overlap করে — তবেই rectangle overlap। (ধার ছোঁয়াকে overlap ধরবে কি না — problem-এর সংজ্ঞা দেখে <= নাকি < ঠিক কোরো।)
আর circle-point আগের squared distance-এরই প্রয়োগ: point টা circle-এর ভেতরে ⟺ dist2(point, center) < r * r — sqrt-এর ছায়াও নেই।
8. Convex hull — rubber band-এর গণিত¶
মেঝেতে কতগুলো পেরেক (point); চারদিক থেকে একটা rubber band টেনে ছেড়ে দাও — band টা বাইরের পেরেকগুলোতে আটকে যে আকার নেয়, সেটাই convex hull। Monotone chain algorithm-এর idea:
- Point গুলো x (tie-তে y) দিয়ে sort করো
- বাঁ থেকে ডানে হেঁটে lower hull গড়ো: নতুন point যোগ করার সময় শেষ দুটো point-এর সাথে বাঁক যদি ভুল দিকে (CCW-এর বদলে CW নয়) যায়, আগেরটা pop — কারণ সে আর সীমানায় নেই
- ডান থেকে বাঁয়ে একইভাবে upper hull; দুটো জুড়লে পুরো hull
def convex_hull(pts):
pts = sorted(set(pts))
if len(pts) <= 2:
return pts
def half(points):
h = []
for p in points:
while len(h) >= 2 and orientation(h[-2], h[-1], p) <= 0:
h.pop() # ভুল দিকে বাঁক → মাঝের point ভেতরে পড়ে গেছে
h.append(p)
return h
lower = half(pts)
upper = half(pts[::-1])
return lower[:-1] + upper[:-1] # জোড়ার point দুবার না গুনে
পুরো শক্তিটা আবার orientation-এ — pop হবে কি না, সেটা cross product-এর sign-ই বলে দেয়। বিস্তারিত প্রমাণ আর variant CP-Algorithms-এ; এখানে rubber band ছবিটা আর "ভুল বাঁকে pop" — এই দুটো নিয়ে গেলেই problem 120 ধরা যাবে।
9. Manhattan distance আর 45° rotation¶
Grid-এ taxi শুধু রাস্তা ধরে চলে — Manhattan distance = |x1−x2| + |y1−y2|। অনেক point-এর মধ্যে maximum Manhattan distance বের করার সরাসরি উপায় O(n²)। Trick: প্রতিটা point-কে ঘুরিয়ে নাও —
তখন |x1−x2| + |y1−y2| = max(|u1−u2|, |v1−v2|) — Manhattan রূপ নেয় Chebyshev distance-এ। আর max-এর হিসাব সোজা: u-এর (max − min) আর v-এর (max − min)-এর বড়টা — O(n)!
def max_manhattan(pts):
us = [x + y for x, y in pts]
vs = [x - y for x, y in pts]
return max(max(us) - min(us), max(vs) - min(vs))
print(max_manhattan([(0, 0), (3, 1), (1, 4)])) # 5 ((0,0) আর (1,4): 1+4)
Mini check: (0,0) → (u,v)=(0,0), (3,1) → (4,2), (1,4) → (5,−3)। u-spread = 5, v-spread = 5 → উত্তর 5 ✓। Identity টা ছোট case-এ নিজে verify করো — |a−b|+|c−d| = max(|(a+c)−(b+d)|, |(a−c)−(b−d)|)-এর sign-এর চারটা case খুলে দেখলেই মিলে যায়।
10. Rotate matrix — পুরো rotation একটা সূত্র¶
n×n matrix 90° clockwise ঘোরালে cell (r, c) কোথায় যায়? কাগজ ঘুরিয়ে দেখো: উপরের সারি ডানের কলাম হয়ে যায় —
def rotate(mat):
n = len(mat)
res = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
res[c][n - 1 - r] = mat[r][c]
return res
In-place চাইলে দুই ধাপ: transpose ((r,c) ↔ (c,r)) তারপর প্রতিটা row reverse — দুটো সহজ operation মিলে rotation। সূত্র মুখস্থ না রেখে এই দুই-ধাপ decomposition মনে রাখাই নিরাপদ।
11. Grid parity — পৌঁছানো সম্ভব কি না, রং দেখে বলো¶
দাবার বোর্ডের মতো grid-এ ঘর গুলোর রং (r + c) % 2। যে চাল প্রতি ধাপে রং বদলায় (যেমন উপরে/নিচে/ডানে/বাঁয়ে 1 ঘর), তাতে k চালের পর তোমার রং = শুরুর রং XOR (k-এর parity)। তাই "ঠিক k চালে (r1,c1) থেকে (r2,c2)" সম্ভব হতে হলে দুটো শর্ত:
def reachable(r1, c1, r2, c2, k):
d = abs(r1 - r2) + abs(c1 - c2) # ন্যূনতম চাল = Manhattan distance
return k >= d and (k - d) % 2 == 0 # বাড়তি চাল জোড়ায় জোড়ায় খরচ হয়
বাড়তি চাল মানে এক ঘর গিয়ে ফিরে আসা — সবসময় 2-এর গুণিতক। এই parity invariant level 0-এর even/odd (problem 001)-এরই বড় ভাই, আর level 11-এর constructive problem-এ "impossible প্রমাণ"-এর প্রধান হাতিয়ার হয়ে ফিরবে।
12. Pick's theorem — area থেকে point গোনা (teaser)¶
Lattice polygon (সব vertex integer point) হলে:
মানে shoelace-এ A আর gcd দিয়ে B (একটা ধার (dx, dy)-তে সীমানা-point থাকে gcd(|dx|, |dy|) টা) বের করলে I ফ্রি: I = A − B/2 + 1। ছোট উদাহরণ — (0,0), (2,0), (0,2) triangle: A = 2, B = 6 (তিন কোণ + প্রতি ধারের মাঝে একটা), তাহলে I = 2 − 3 + 1 = 0 — সত্যিই ভেতরে কোনো integer point নেই ✓। গভীর প্রমাণ problem 124-এ; এখানে শুধু সূত্রের তিন রাশির মানে চিনে রাখো।
এক নজরে building block গুলো¶
block কী দেয় কোথায় লাগে
──────────────────────────────────────────────────────────────────
squared distance sqrt-হীন তুলনা 113, 119, nearest point
cross multiplication ভাগ-হীন slope তুলনা 114
cross product orientation + area 116, 117, 120, 115
shoelace polygon area 115, 124
interval logic প্রতি axis আলাদা 118
(x+y, x−y) Manhattan → Chebyshev 121
(r,c) → (c,n−1−r) 90° rotation 122
(r+c) % 2 parity invariant 123
পরের ধাপ: visualization-ideas.md-তে এই ছবিগুলোই আরো বড় করে আঁকা আছে — geometry-তে ছবিই অর্ধেক সমাধান।