# Concept Notes — Geometry & Coordinate Math (এক অস্ত্রে অনেক যুদ্ধ) ## সহজ করে শুরু: ছবি থেকে নির্ভুল তুলনা দূরত্ব তুলনা করতে square root না নিয়ে squared distance তুলনা করা যায়। তিন বিন্দুর বাঁক বুঝতে cross product: `(Bx-Ax)*(Cy-Ay)-(By-Ay)*(Cx-Ax)`। Cartesian y ওপরের দিকে হলে positive মানে বাঁয়ে বাঁক। **প্রোগ্রামে কোথায় ব্যবহার করবে:** মানচিত্রে point-এর অবস্থান, game collision-এর সহজ পরীক্ষা, rectangle overlap এবং কয়েকটি বিন্দুকে ঘিরে boundary তৈরিতে লাগে। **কৌশল বাছার আগে শর্ত:** Screen-এ y নিচের দিকে বাড়লে দৃশ্যমান বাঁকের sign উল্টো মনে হতে পারে। রেখা ও সীমিত segment এক জিনিস নয়। Boundary ছোঁয়া overlap হিসেবে ধরবে কি না, শুরুতে লিখবে। পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও। > এই 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-র দিকে একটা তীর: ```python 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 ``` ```text y 4 | B(4,3) 3 | ↗ 2 | ↗ AB = (3, 2) 1 | A(1,1) └─────────────── x ``` এই তীর-ভাবনাটাই সব কিছুর ভিত্তি: "তিনটা point কেমন সাজানো" প্রশ্নটা আসলে "দুটো তীর একে অপরের তুলনায় কোন দিকে বাঁকা" প্রশ্ন। ## 2. Squared distance — sqrt-কে বিদায় দূরত্বের সূত্র `√(dx² + dy²)` — কিন্তু `√` মানেই float। আর float তুলনা মানেই বিপদ। সুখবর: **দূরত্ব তুলনা করতে sqrt লাগেই না**, কারণ দুটো অঋণাত্মক সংখ্যায় `a < b ⟺ a² < b²`। ```python 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 মিলিয়ে দেখো। কিন্তু: ```python slope_AB = (B[1] - A[1]) / (B[0] - A[0]) # B[0] == A[0] হলে? ZeroDivisionError! ``` Vertical line-এ এই formula ভেঙে পড়ে, আর float division-এ `1/3` আর `0.333...` মেলে না। সমাধান: ভাগটা **cross multiplication**-এ বদলাও। `(y2−y1)/(x2−x1) == (y3−y1)/(x3−x1)` — দুই পাশে গুণ করে: ```python 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: ```python def cross(u, v): return u[0] * v[1] - u[1] * v[0] ``` এই একটা সংখ্যার দুটো অর্থ: 1. **|cross| = u আর v দিয়ে বানানো parallelogram-এর area** (triangle-এর double area) 2. **sign বলে দেয় v vector-টা u-এর তুলনায় কোন দিকে বাঁকা** তিনটা point A, B, C-র জন্য orientation: ```python 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 উপরে বাড়ে): ```text CCW (+1): C CW (−1): A───▶B collinear (0): ▲ ╲ │ বাঁয়ে বাঁক ╲ ডানে A───B───C A───▶B ▼ C ``` 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 (জুতার ফিতার মতো আড়াআড়ি গুণ): ```python 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 মেলানোর দরকার নেই। প্রশ্ন চারটা: ```text R আর S কি PQ-এর দুই পাশে? → orientation(P,Q,R) ≠ orientation(P,Q,S) P আর Q কি RS-এর দুই পাশে? → orientation(R,S,P) ≠ orientation(R,S,Q) ``` দুটোই হ্যাঁ হলে কাটে। ছবিতে: ```text R R S │ (PQ-এর উপরে) ╲ ╱ ← দুজনেই একই পাশে: P───────┼───────Q P──────╳────Q কাটে না (প্রথম শর্ত fail) │ (এখানে আসলে R,S দুটোই উপরে) S (নিচে) → কাটে ✓ ``` ```python 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 করে না?** — একটা পুরোপুরি অন্যটার বাঁয়ে / ডানে / উপরে / নিচে থাকলে: ```python def overlap(A, B): no = A[2] <= B[0] or B[2] <= A[0] or A[3] <= B[1] or B[3] <= A[1] return not no ``` আসলে এটা প্রতি 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: 1. Point গুলো x (tie-তে y) দিয়ে sort করো 2. বাঁ থেকে ডানে হেঁটে **lower hull** গড়ো: নতুন point যোগ করার সময় শেষ দুটো point-এর সাথে বাঁক যদি ভুল দিকে (CCW-এর বদলে CW নয়) যায়, আগেরটা pop — কারণ সে আর সীমানায় নেই 3. ডান থেকে বাঁয়ে একইভাবে **upper hull**; দুটো জুড়লে পুরো hull ```python 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-কে ঘুরিয়ে নাও — ```python u, v = x + y, x - y # 45° rotation (সাথে scale, তাতে ক্ষতি নেই) ``` তখন `|x1−x2| + |y1−y2| = max(|u1−u2|, |v1−v2|)` — Manhattan রূপ নেয় **Chebyshev** distance-এ। আর max-এর হিসাব সোজা: u-এর (max − min) আর v-এর (max − min)-এর বড়টা — O(n)! ```python 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)` কোথায় যায়? কাগজ ঘুরিয়ে দেখো: উপরের সারি ডানের কলাম হয়ে যায় — ```text (r, c) → (c, n−1−r) আগে: a b c পরে: g d a d e f h e b g h i i f c (0,0)-র a গেল (0,2)-তে ✓ ``` ```python 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)" সম্ভব হতে হলে দুটো শর্ত: ```python 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) হলে: ```text A = I + B/2 − 1 A = area (shoelace দিয়ে), I = ভেতরের lattice point, B = সীমানার lattice 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 গুলো ```text 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](visualization-ideas.md)-তে এই ছবিগুলোই আরো বড় করে আঁকা আছে — geometry-তে ছবিই অর্ধেক সমাধান।