# Level 9 — Geometry & Coordinate Math (ছবি এঁকে অঙ্ক)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> 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](problems/113-distance-between-points.md) | squared distance | Classic exercise |
| 114 | [Slope and Collinearity](problems/114-slope-and-collinearity.md) | cross multiply | Classic exercise |
| 115 | [Area of Triangle](problems/115-area-of-triangle.md) | shoelace | Classic exercise |
| 119 | [Circle and Point](problems/119-circle-and-point.md) | r² compare | Classic exercise |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 116 | [Orientation of Three Points](problems/116-orientation-three-points.md) | cross product sign | CP-Algorithms — <https://cp-algorithms.com/geometry/oriented-triangle-area.html> |
| 117 | [Line Intersection Basic](problems/117-line-intersection-basic.md) | orientation test | CP-Algorithms geometry — <https://cp-algorithms.com/geometry/check-segments-intersection.html> |
| 118 | [Rectangle Overlap](problems/118-rectangle-overlap.md) | interval logic | LeetCode — <https://leetcode.com/problems/rectangle-overlap/> |
| 121 | [Manhattan Distance Tricks](problems/121-manhattan-distance-tricks.md) | 45° rotation | Classic CP trick |
| 122 | [Rotate Matrix and Coordinates](problems/122-rotate-matrix-coordinates.md) | coordinate map | LeetCode Rotate Image — <https://leetcode.com/problems/rotate-image/> |
| 123 | [Grid Movement Math](problems/123-grid-movement-math.md) | parity reachability | Classic exercise |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 120 | [Convex Hull Intro](problems/120-convex-hull-intro.md) | 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](problems/124-picks-theorem-intro.md) | lattice counting | CP-Algorithms — <https://cp-algorithms.com/geometry/picks-theorem.html> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **113 → 119** — squared distance-এর অভ্যাস; circle-point আসলে distance-এরই জমজ
2. **114 → 115** — slope-এর বিপদ আর cross multiplication, তারপর shoelace — একই সূত্রের দুই চেহারা
3. **116** — cross product-এর sign; এটাই level-এর কেন্দ্র, সময় নিয়ে করো
4. **117** — orientation দিয়ে segment intersection; 116 পরিষ্কার থাকলে এটা শুধু case সাজানো
5. **118 → 122** — interview-ঘরানার দুটো: interval logic আর coordinate map
6. **121 → 123** — Manhattan trick আর grid parity — CP-র মশলা
7. **120 → 124** — শেষে দুটো Hard: convex hull আর Pick's theorem; দুটোই আগের সবকিছুর সমাবেশ

## Common mistakes (সাধারণ ভুল)

1. **দূরত্বে অকারণে sqrt নেওয়া** — তুলনার জন্য squared distance-ই যথেষ্ট; sqrt মানেই float, আর float মানেই `0.30000000000000004`-এর দুঃস্বপ্ন।
2. **Slope-এ ভাগ করা** — `x2 == x1` হলে ZeroDivisionError; আর float slope-এ `1/3 == 0.3333...` মেলে না। সবসময় cross multiplication।
3. **Cross product-এর sign convention গুলিয়ে ফেলা** — positive মানে CCW (standard math axes-এ); নিজের convention একবার ঠিক করে comment-এ লিখে রাখো, আর screen-coordinate (y নিচে বাড়ে) হলে উল্টে যায় — সাবধান।
4. **Segment intersection-এ collinear case ভুলে যাওয়া** — চারটা orientation-ই 0 হলে আলাদা করে দেখতে হয় segment দুটো overlap করে কি না; এই special case-ই বেশিরভাগ WA-র উৎস।
5. **Rectangle overlap-এ touch নিয়ে গোলমাল** — শুধু ধার ছুঁলে overlap ধরা হবে কি না, problem-এর সংজ্ঞা না পড়ে `<` আর `<=` মিশিয়ে ফেলা।
6. **Shoelace-এ abs আর ÷2 ভুলে যাওয়া** — cross product-এর যোগফল signed আর double area দেয়; area চাইলে `abs(...) / 2`, আর integer রাখতে চাইলে doubled area নিয়েই কাজ করো।
7. **Rotate matrix-এ in-place করতে গিয়ে value চাপা দেওয়া** — নতুন matrix-এ map করা সহজ; in-place চাইলে transpose + reverse-এর দুই ধাপ, একসাথে করতে গেলে গোলমাল।
8. **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](../10-advanced-number-theory/README.md)-এ। (মনে রেখো: level 10-11 interview-এর জন্য optional — চাইলে আগে মূল DS topic গুলোতেও যেতে পারো।)

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।