Level 9 — Geometry & Coordinate Math (ছবি এঁকে অঙ্ক)¶
Geometry-র problem-এ ভয় পাওয়ার মূল কারণ formula মুখস্থের চাপ। কিন্তু আসল রহস্য একটাই অস্ত্রে — cross product। এই level-এ আমরা শিখব কীভাবে গোটা coordinate geometry-কে কয়েকটা ছোট building block-এ নামিয়ে আনা যায়, আর কোথায় floating point-এর ফাঁদ লুকিয়ে থাকে।
এই level এ কী শিখবে?¶
Coordinate geometry মানে point, line, triangle, rectangle, circle — সব কিছুকে সংখ্যা দিয়ে ধরা। Programming-এ এর সৌন্দর্য হলো: হাতে-আঁকা ছবির প্রতিটা প্রশ্নের ("এই তিনটা point কি এক লাইনে?", "এই দুটো segment কি কাটে?") একটা ছোট, integer-only সূত্র আছে — sqrt বা ভাগ ছাড়াই।
মূল idea গুলো:
- Point = ছোট vector — point-কে tuple ভাবো, point বিয়োগ মানে এক point থেকে আরেকটার দিকে তীর
- Squared distance — দূরত্ব তুলনা করতে sqrt লাগে না;
dx² + dy²integer-এ রাখো, precision bug শূন্য - Slope-এর বিপদ — vertical line-এ ভাগে শূন্য! ভাগ না করে cross multiplication:
(y2−y1)(x3−x1) == (y3−y1)(x2−x1) - Cross product = signed area ×2 — তিন point-এর orientation (CW / CCW / collinear) এক sign দেখে বোঝা — এই level-এর হৃদপিণ্ড
- Shoelace — triangle (এবং polygon) area cross product-এরই যোগফল
- Segment intersection — orientation test চারবার চালিয়ে কাটাকাটি ধরা, equation মেলানোর দরকারই নেই
- Rectangle overlap — 2D প্রশ্নটা আসলে দুটো 1D interval overlap; negation trick-এ ("কখন overlap করে না") সহজ
- Convex hull — rubber band-এর ছবি: সব point ঘিরে রবার ছাড়লে যে আকার, সেটাই hull (monotone chain idea)
- Manhattan distance — grid taxi-র দূরত্ব; 45° rotation
(x+y, x−y)করলে max-distance প্রশ্ন সহজ হয়ে যায় - Matrix rotation = coordinate map —
(r, c) → (c, n−1−r)— পুরো rotation একটা ছোট সূত্র - Grid parity — গন্তব্যে পৌঁছানো যাবে কি না, অনেক সময় শুধু জোড়-বিজোড় দেখে বলা যায়
- Pick's theorem teaser — lattice polygon-এ
A = I + B/2 − 1— area থেকে ভেতরের point গোনা
কেন এই level দরকার?¶
Competitive programming (CP) এ: Codeforces আর CSES-এ geometry একটা নিয়মিত category। Orientation, convex hull, shoelace — এগুলো ছাড়া geometry tag-এর problem ছোঁয়াই যায় না। আর integer-only কৌশল (squared distance, cross multiplication) জানা না থাকলে precision-এর WA খেতে খেতে জীবন যায়।
Interview এ: Rectangle Overlap, Rotate Image, K Closest Points — এগুলো common interview pattern। Geometry-ভারী প্রশ্ন interview-তে কম, কিন্তু যেগুলো আসে সেগুলোতে coordinate transform আর interval logic-এর পরিষ্কার চিন্তাই পরীক্ষা হয়।
পরের level গুলোতে: Level 11-এর constructive problem-এ grid parity আর invariant ফিরে আসবে; আর পরের DS topic গুলোতে (matrix traversal, grid BFS — ../../09-graphs/) coordinate-এ স্বচ্ছন্দ থাকাটা ধরে নেওয়া হবে।
Prerequisites¶
- Level 0–8 শেষ করা — বিশেষ করে:
- Level 0-এর parity (123-এ লাগবে)
- Level 8-এর sort + greedy অভ্যাস (convex hull-এ sort প্রথম ধাপ)
- Tuple, list of tuples, আর
sort(key=...)Python-এ স্বচ্ছন্দ - স্কুলের coordinate geometry-র হালকা স্মৃতি থাকলেই যথেষ্ট — formula মুখস্থ লাগবে না, আমরা সব নতুন করে গড়ব
Learning goals (checklist)¶
এই level শেষে নিজেকে জিজ্ঞেস করো:
- [ ] দুটো দূরত্ব তুলনা করতে কেন sqrt লাগে না — এক লাইনে বলতে পারি
- [ ] Vertical line-এ slope formula কেন ভাঙে, আর cross multiplication কীভাবে বাঁচায় — উদাহরণসহ জানি
- [ ] Cross product-এর sign থেকে CW / CCW / collinear — তিনটা case ছবি এঁকে দেখাতে পারি
- [ ] Shoelace formula দিয়ে triangle-এর area হাতে হিসাব করতে পারি
- [ ] দুটো segment কাটে কি না — orientation test দিয়ে check-এর কাঠামো লিখতে পারি (collinear special case সহ)
- [ ] Rectangle overlap-এর negation trick ("overlap করে না কখন?") নিজের ভাষায় বলতে পারি
- [ ] Convex hull-এর rubber band ছবিটা আঁকতে পারি, আর monotone chain-এ "বাঁক ভুল দিকে গেলে pop" idea-টা বুঝি
- [ ] Manhattan distance-এর 45° rotation
(x+y, x−y)কী সমস্যা সহজ করে — জানি - [ ] Rotate matrix-এর
(r, c) → (c, n−1−r)map টা একটা 3×3 উদাহরণে হাতে চালিয়েছি
Problem list¶
মোট 12টা problem — 4টা Easy, 6টা Medium, 2টা Hard।
Easy¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 113 | Distance Between Points | squared distance | Classic exercise |
| 114 | Slope and Collinearity | cross multiply | Classic exercise |
| 115 | Area of Triangle | shoelace | Classic exercise |
| 119 | Circle and Point | r² compare | Classic exercise |
Medium¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 116 | Orientation of Three Points | cross product sign | CP-Algorithms — https://cp-algorithms.com/geometry/oriented-triangle-area.html |
| 117 | Line Intersection Basic | orientation test | CP-Algorithms geometry — https://cp-algorithms.com/ |
| 118 | Rectangle Overlap | interval logic | LeetCode — https://leetcode.com/problems/rectangle-overlap/ |
| 121 | Manhattan Distance Tricks | 45° rotation | Classic CP trick |
| 122 | Rotate Matrix and Coordinates | coordinate map | LeetCode Rotate Image — https://leetcode.com/problems/rotate-image/ |
| 123 | Grid Movement Math | parity reachability | Classic exercise |
Hard¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 120 | Convex Hull Intro | monotone chain | CP-Algorithms — https://cp-algorithms.com/geometry/convex-hull.html, CSES Convex Hull — https://cses.fi/problemset/task/2195 |
| 124 | Pick's Theorem Intro | lattice counting | CP-Algorithms — https://cp-algorithms.com/geometry/picks-theorem.html |
পুরো tracker table (status সহ) আছে problems/README.md-তে।
Recommended order¶
- 113 → 119 — squared distance-এর অভ্যাস; circle-point আসলে distance-এরই জমজ
- 114 → 115 — slope-এর বিপদ আর cross multiplication, তারপর shoelace — একই সূত্রের দুই চেহারা
- 116 — cross product-এর sign; এটাই level-এর কেন্দ্র, সময় নিয়ে করো
- 117 — orientation দিয়ে segment intersection; 116 পরিষ্কার থাকলে এটা শুধু case সাজানো
- 118 → 122 — interview-ঘরানার দুটো: interval logic আর coordinate map
- 121 → 123 — Manhattan trick আর grid parity — CP-র মশলা
- 120 → 124 — শেষে দুটো Hard: convex hull আর Pick's theorem; দুটোই আগের সবকিছুর সমাবেশ
Common mistakes (সাধারণ ভুল)¶
- দূরত্বে অকারণে sqrt নেওয়া — তুলনার জন্য squared distance-ই যথেষ্ট; sqrt মানেই float, আর float মানেই
0.30000000000000004-এর দুঃস্বপ্ন। - Slope-এ ভাগ করা —
x2 == x1হলে ZeroDivisionError; আর float slope-এ1/3 == 0.3333...মেলে না। সবসময় cross multiplication। - Cross product-এর sign convention গুলিয়ে ফেলা — positive মানে CCW (standard math axes-এ); নিজের convention একবার ঠিক করে comment-এ লিখে রাখো, আর screen-coordinate (y নিচে বাড়ে) হলে উল্টে যায় — সাবধান।
- Segment intersection-এ collinear case ভুলে যাওয়া — চারটা orientation-ই 0 হলে আলাদা করে দেখতে হয় segment দুটো overlap করে কি না; এই special case-ই বেশিরভাগ WA-র উৎস।
- Rectangle overlap-এ touch নিয়ে গোলমাল — শুধু ধার ছুঁলে overlap ধরা হবে কি না, problem-এর সংজ্ঞা না পড়ে
<আর<=মিশিয়ে ফেলা। - Shoelace-এ abs আর ÷2 ভুলে যাওয়া — cross product-এর যোগফল signed আর double area দেয়; area চাইলে
abs(...) / 2, আর integer রাখতে চাইলে doubled area নিয়েই কাজ করো। - Rotate matrix-এ in-place করতে গিয়ে value চাপা দেওয়া — নতুন matrix-এ map করা সহজ; in-place চাইলে transpose + reverse-এর দুই ধাপ, একসাথে করতে গেলে গোলমাল।
- Convex hull-এ duplicate point আর সব collinear point-এর edge case — n ≤ 2 বা সব point এক লাইনে — এগুলো আগে handle না করলে hull ভেঙে পড়ে।
পরের level এ যাওয়ার আগে checklist¶
- [ ] 12টা problem-ই অন্তত একবার নিজে solve করেছি
- [ ] Cross product-এর sign দিয়ে orientation — না দেখে লিখতে পারি
- [ ] Segment intersection-এর সব case (general + collinear) কাগজে এঁকে list করেছি
- [ ] Rectangle overlap-এর negation trick এক লাইনে লিখতে পারি
- [ ] Convex hull-এর monotone chain-এ কেন point pop হয় — ছবি এঁকে বুঝিয়েছি
- [ ]
(x+y, x−y)rotation-এ Manhattan কেন Chebyshev হয়ে যায় — একটা উদাহরণে হাতে দেখেছি - [ ] Pick's theorem-এর তিনটা রাশি (A, I, B) একটা ছোট polygon-এ গুনে মিলিয়েছি
সব টিক দিতে পারলে — চলো Level 10: Advanced Number Theory-এ। (মনে রেখো: level 10-11 interview-এর জন্য optional — চাইলে আগে মূল DS topic গুলোতেও যেতে পারো।)
Source map¶
এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।