{"title":"Chapter 10: Geometry","description":"","content":"# Chapter 10: Geometry\n\nGiven a million points on a plane, find the two closest ones. The brute force approach checks every pair, giving you O(n^2). But with the right geometric insight, you can solve it in O(n log n). Geometry problems in interviews test whether you can translate spatial reasoning into clean, efficient code.\n\nWhat makes geometry tricky is not the math itself. Most of it is high school level. The challenge is avoiding pitfalls like floating point errors, division by zero with vertical lines, and edge cases that silently break your logic. The good news is that a handful of core techniques, distance formulas, cross products, and the Shoelace formula, cover the vast majority of interview problems.\n\nIn this chapter, we will build up from basic distance calculations to orientation detection, line segment intersection, and convex hulls. By the end, you will have a solid toolkit for tackling any computational geometry problem that shows up in an interview.\n\n---\n\n## Why It Matters\n\nGeometry problems appear more often in interviews than most candidates expect. Problems like \"Max Points on a Line,\" \"Valid Square,\" \"Rectangle Overlap,\" and \"Minimum Area Rectangle\" all require geometric reasoning. They test your ability to think spatially and then express that thinking in code.\n\n**Interview Insight:** Interviewers use geometry problems to assess whether you can avoid common traps. The classic mistake on \"Max Points on a Line\" is using floating point slopes. Candidates who know the cross product trick immediately stand out.\n\nBeyond interviews, computational geometry powers collision detection in games, geographic information systems, computer graphics, and robotics. The fundamentals we cover here are the same ones used in production systems worldwide.\n\n---\n\n## Core Concepts\n\n### Distance Formulas\n\nThe two distance formulas you need to know are Euclidean distance and Manhattan distance.\n\n**Euclidean distance** is the straight line distance between two points (x1, y1) and (x2, y2):\n\n\n```shell\nd = sqrt((x2 - x1)^2 + (y2 - y1)^2)\n```\n\n\n**Manhattan distance** (also called taxicab distance) measures distance along axis-aligned paths:\n\n\n```shell\nd = |x2 - x1| + |y2 - y1|\n```\n\n\nWhen should you use each? Euclidean distance is the default for \"real\" distance. Manhattan distance is useful in grid-based problems where you can only move horizontally or vertically, like a taxi navigating city blocks.\n\n**Interview Insight:** When comparing Euclidean distances, you can often skip the square root entirely and compare squared distances instead. This avoids floating point issues and is faster. If `d1^2 < d2^2`, then `d1 < d2`.\n\n\n```mermaid\nflowchart TD\n subgraph Euclidean[\"Euclidean Distance\"]\n A[\"Point A (1, 1)\"]:::primary\n B[\"Point B (4, 5)\"]:::primary\n E[\"d = sqrt(9 + 16) = 5.0\"]:::green\n end\n\n subgraph Manhattan[\"Manhattan Distance\"]\n C[\"Point A (1, 1)\"]:::orange\n D[\"Point B (4, 5)\"]:::orange\n M[\"d = |3| + |4| = 7\"]:::green\n end\n\n A --> E\n B --> E\n C --> M\n D --> M\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Cross Product and Orientation\n\nThe cross product is the single most important tool in computational geometry. Given three points P1, P2, and P3, the cross product of vectors (P1 -> P2) and (P1 -> P3) tells you the orientation of the triplet.\n\n\n```shell\ncross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)\n```\n\n\nThe result tells you three things:\n\n- **cross > 0**: The points make a counterclockwise (left) turn\n- **cross < 0**: The points make a clockwise (right) turn\n- **cross == 0**: The points are collinear (on the same line)\n\nThis is powerful because it avoids division entirely. No division means no division-by-zero errors, no floating point imprecision, and no special-casing for vertical lines.\n\n\n```mermaid\nflowchart LR\n subgraph CCW[\"Counterclockwise
cross > 0\"]\n P1a[\"P1\"]:::primary\n P2a[\"P2\"]:::primary\n P3a[\"P3 (left)\"]:::green\n end\n\n subgraph CW[\"Clockwise
cross < 0\"]\n P1b[\"P1\"]:::primary\n P2b[\"P2\"]:::primary\n P3b[\"P3 (right)\"]:::red\n end\n\n subgraph COL[\"Collinear
cross == 0\"]\n P1c[\"P1\"]:::primary\n P2c[\"P2\"]:::primary\n P3c[\"P3 (on line)\"]:::orange\n end\n\n P1a --> P2a --> P3a\n P1b --> P2b --> P3b\n P1c --> P2c --> P3c\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Collinearity Check\n\nThree points are collinear if the cross product is zero. This is the correct way to check if points lie on the same line, not by computing and comparing slopes.\n\nWhy not slopes? Because slope = (y2 - y1) / (x2 - x1) breaks when x2 == x1 (vertical line) and introduces floating point errors when the coordinates are large. The cross product method works with integer arithmetic and handles all cases uniformly.\n\n---\n\n## Detailed Explanation\n\n### Line Segment Intersection\n\nTwo line segments intersect if and only if they \"straddle\" each other. Segment AB straddles segment CD if points C and D are on opposite sides of line AB. And segment CD straddles segment AB if points A and B are on opposite sides of line CD.\n\nWe check this using orientation. For segments (P1, P2) and (P3, P4):\n\n1. Compute `o1` = orientation(P1, P2, P3)\n2. Compute `o2` = orientation(P1, P2, P4)\n3. Compute `o3` = orientation(P3, P4, P1)\n4. Compute `o4` = orientation(P3, P4, P2)\n\nThe segments intersect if:\n\n- `o1` and `o2` have different signs (P3 and P4 straddle the line through P1P2), AND\n- `o3` and `o4` have different signs (P1 and P2 straddle the line through P3P4)\n\nThere is a special case when one of the orientations is zero, meaning a point lies exactly on the other segment. In that case, we need to check if the point is within the bounding box of the segment.\n\n### Triangle Area (Shoelace Formula)\n\nGiven three vertices (x1, y1), (x2, y2), (x3, y3), the area of the triangle is:\n\n\n```shell\nArea = 0.5 * |x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)|\n```\n\n\nThis is a special case of the Shoelace formula, which computes the area of any polygon given its vertices. The absolute value is important because the raw formula gives a signed area (positive for counterclockwise, negative for clockwise).\n\nThe Shoelace formula generalizes to any polygon with n vertices:\n\n\n```shell\nArea = 0.5 * |sum of (xi * y(i+1) - x(i+1) * yi) for i = 0 to n-1|\n```\n\n\nwhere indices wrap around (vertex n is vertex 0).\n\n### Convex Hull\n\nThe convex hull of a set of points is the smallest convex polygon that contains all the points. Think of it as stretching a rubber band around all the points and letting it snap tight.\n\nAndrew's monotone chain algorithm builds the convex hull in O(n log n):\n\n1. Sort the points by x-coordinate (break ties by y-coordinate).\n2. Build the lower hull by iterating left to right. For each point, while the last two points in the hull and the new point make a clockwise turn (or are collinear), remove the last point.\n3. Build the upper hull by iterating right to left with the same logic.\n4. Concatenate the lower and upper hulls.\n\nThe key operation in step 2 and 3 is the cross product check. If the cross product is non-positive (clockwise or collinear), we pop the last point from the hull.\n\n\n```mermaid\nflowchart TD\n S[\"Sort points by x-coordinate\"]:::primary\n L[\"Build lower hull
(left to right)\"]:::teal\n U[\"Build upper hull
(right to left)\"]:::teal\n C[\"Cross product check:
clockwise turn? Remove point\"]:::orange\n R[\"Concatenate lower + upper hull\"]:::green\n\n S --> L\n S --> U\n L --> C\n U --> C\n C --> R\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n## Example Walkthrough\n\n### Detecting Orientation of Three Points\n\nLet us work through orientation detection with concrete points.\n\n**Points:** P1 = (0, 0), P2 = (4, 4), P3 = (1, 2)\n\n\n```shell\ncross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)\ncross = (4 - 0) * (2 - 0) - (4 - 0) * (1 - 0)\ncross = 4 * 2 - 4 * 1\ncross = 8 - 4\ncross = 4\n```\n\n\nSince cross > 0, the orientation is **counterclockwise**. P3 lies to the left of the line from P1 to P2.\n\nNow let us try P3 = (2, 1):\n\n\n```shell\ncross = (4 - 0) * (1 - 0) - (4 - 0) * (2 - 0)\ncross = 4 * 1 - 4 * 2\ncross = 4 - 8\ncross = -4\n```\n\n\nSince cross < 0, the orientation is **clockwise**. P3 lies to the right of the line from P1 to P2.\n\nFinally, P3 = (2, 2):\n\n\n```shell\ncross = (4 - 0) * (2 - 0) - (4 - 0) * (2 - 0)\ncross = 8 - 8\ncross = 0\n```\n\n\nCross product is zero, so the three points are **collinear**.\n\n### Checking Line Segment Intersection\n\n**Segment 1:** A = (1, 1), B = (4, 4) **Segment 2:** C = (1, 4), D = (4, 1)\n\n\n```shell\nStep 1: o1 = orientation(A, B, C)\n cross = (4-1)*(4-1) - (4-1)*(1-1) = 9 - 0 = 9 > 0 --> CCW\n\nStep 2: o2 = orientation(A, B, D)\n cross = (4-1)*(1-1) - (4-1)*(4-1) = 0 - 9 = -9 < 0 --> CW\n\nStep 3: o3 = orientation(C, D, A)\n cross = (4-1)*(1-4) - (1-4)*(1-1) = 3*(-3) - (-3)*0 = -9 < 0 --> CW\n\nStep 4: o4 = orientation(C, D, B)\n cross = (4-1)*(4-4) - (1-4)*(4-1) = 0 - (-9) = 9 > 0 --> CCW\n```\n\n\no1 and o2 have different signs (CCW and CW). o3 and o4 have different signs (CW and CCW). Therefore, the segments **intersect**.\n\n---\n\n## Implementation\n\nBelow are implementations of the core geometric operations: Euclidean distance, Manhattan distance, cross product / orientation, collinearity check, and triangle area.\n\n### Java\n\n\n```java\npublic class Geometry {\n\n // Euclidean distance (squared to avoid floating point)\n public static double euclideanDistance(int x1, int y1, int x2, int y2) {\n int dx = x2 - x1;\n int dy = y2 - y1;\n return Math.sqrt((long) dx * dx + (long) dy * dy);\n }\n\n // Manhattan distance\n public static int manhattanDistance(int x1, int y1, int x2, int y2) {\n return Math.abs(x2 - x1) + Math.abs(y2 - y1);\n }\n\n // Cross product of vectors (p1->p2) and (p1->p3)\n // Returns positive for CCW, negative for CW, zero for collinear\n public static long crossProduct(int[] p1, int[] p2, int[] p3) {\n return (long)(p2[0] - p1[0]) * (p3[1] - p1[1])\n - (long)(p2[1] - p1[1]) * (p3[0] - p1[0]);\n }\n\n // Orientation: 0 = collinear, 1 = clockwise, 2 = counterclockwise\n public static int orientation(int[] p1, int[] p2, int[] p3) {\n long cross = crossProduct(p1, p2, p3);\n if (cross == 0) return 0;\n return cross > 0 ? 2 : 1;\n }\n\n // Check if three points are collinear\n public static boolean areCollinear(int[] p1, int[] p2, int[] p3) {\n return crossProduct(p1, p2, p3) == 0;\n }\n\n // Area of triangle using Shoelace formula\n public static double triangleArea(int[] p1, int[] p2, int[] p3) {\n long area2 = Math.abs(\n (long) p1[0] * (p2[1] - p3[1])\n + (long) p2[0] * (p3[1] - p1[1])\n + (long) p3[0] * (p1[1] - p2[1])\n );\n return area2 / 2.0;\n }\n}\n```\n\n\n### Python\n\n\n```python\nimport math\n\ndef euclidean_distance(x1, y1, x2, y2):\n dx = x2 - x1\n dy = y2 - y1\n return math.sqrt(dx * dx + dy * dy)\n\ndef manhattan_distance(x1, y1, x2, y2):\n return abs(x2 - x1) + abs(y2 - y1)\n\ndef cross_product(p1, p2, p3):\n \"\"\"Returns positive for CCW, negative for CW, zero for collinear.\"\"\"\n return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])\n\ndef orientation(p1, p2, p3):\n \"\"\"0 = collinear, 1 = clockwise, 2 = counterclockwise.\"\"\"\n cross = cross_product(p1, p2, p3)\n if cross == 0:\n return 0\n return 2 if cross > 0 else 1\n\ndef are_collinear(p1, p2, p3):\n return cross_product(p1, p2, p3) == 0\n\ndef triangle_area(p1, p2, p3):\n area2 = abs(\n p1[0] * (p2[1] - p3[1])\n + p2[0] * (p3[1] - p1[1])\n + p3[0] * (p1[1] - p2[1])\n )\n return area2 / 2.0\n```\n\n\n### C++\n\n\n```cpp\n#include \n#include \n#include \n\nusing namespace std;\n\ndouble euclideanDistance(int x1, int y1, int x2, int y2) {\n long long dx = x2 - x1;\n long long dy = y2 - y1;\n return sqrt(dx * dx + dy * dy);\n}\n\nint manhattanDistance(int x1, int y1, int x2, int y2) {\n return abs(x2 - x1) + abs(y2 - y1);\n}\n\n// Returns positive for CCW, negative for CW, zero for collinear\nlong long crossProduct(vector& p1, vector& p2, vector& p3) {\n return (long long)(p2[0] - p1[0]) * (p3[1] - p1[1])\n - (long long)(p2[1] - p1[1]) * (p3[0] - p1[0]);\n}\n\n// 0 = collinear, 1 = clockwise, 2 = counterclockwise\nint orientation(vector& p1, vector& p2, vector& p3) {\n long long cross = crossProduct(p1, p2, p3);\n if (cross == 0) return 0;\n return cross > 0 ? 2 : 1;\n}\n\nbool areCollinear(vector& p1, vector& p2, vector& p3) {\n return crossProduct(p1, p2, p3) == 0;\n}\n\ndouble triangleArea(vector& p1, vector& p2, vector& p3) {\n long long area2 = abs(\n (long long)p1[0] * (p2[1] - p3[1])\n + (long long)p2[0] * (p3[1] - p1[1])\n + (long long)p3[0] * (p1[1] - p2[1])\n );\n return area2 / 2.0;\n}\n```\n\n\n### C#\n\n\n```csharp\nusing System;\n\npublic class Geometry {\n\n public static double EuclideanDistance(int x1, int y1, int x2, int y2) {\n long dx = x2 - x1;\n long dy = y2 - y1;\n return Math.Sqrt(dx * dx + dy * dy);\n }\n\n public static int ManhattanDistance(int x1, int y1, int x2, int y2) {\n return Math.Abs(x2 - x1) + Math.Abs(y2 - y1);\n }\n\n // Returns positive for CCW, negative for CW, zero for collinear\n public static long CrossProduct(int[] p1, int[] p2, int[] p3) {\n return (long)(p2[0] - p1[0]) * (p3[1] - p1[1])\n - (long)(p2[1] - p1[1]) * (p3[0] - p1[0]);\n }\n\n // 0 = collinear, 1 = clockwise, 2 = counterclockwise\n public static int Orientation(int[] p1, int[] p2, int[] p3) {\n long cross = CrossProduct(p1, p2, p3);\n if (cross == 0) return 0;\n return cross > 0 ? 2 : 1;\n }\n\n public static bool AreCollinear(int[] p1, int[] p2, int[] p3) {\n return CrossProduct(p1, p2, p3) == 0;\n }\n\n public static double TriangleArea(int[] p1, int[] p2, int[] p3) {\n long area2 = Math.Abs(\n (long)p1[0] * (p2[1] - p3[1])\n + (long)p2[0] * (p3[1] - p1[1])\n + (long)p3[0] * (p1[1] - p2[1])\n );\n return area2 / 2.0;\n }\n}\n```\n\n\n### JavaScript\n\n\n```javascript\nfunction euclideanDistance(x1, y1, x2, y2) {\n const dx = x2 - x1;\n const dy = y2 - y1;\n return Math.sqrt(dx * dx + dy * dy);\n}\n\nfunction manhattanDistance(x1, y1, x2, y2) {\n return Math.abs(x2 - x1) + Math.abs(y2 - y1);\n}\n\n// Returns positive for CCW, negative for CW, zero for collinear\nfunction crossProduct(p1, p2, p3) {\n return (p2[0] - p1[0]) * (p3[1] - p1[1])\n - (p2[1] - p1[1]) * (p3[0] - p1[0]);\n}\n\n// 0 = collinear, 1 = clockwise, 2 = counterclockwise\nfunction orientation(p1, p2, p3) {\n const cross = crossProduct(p1, p2, p3);\n if (cross === 0) return 0;\n return cross > 0 ? 2 : 1;\n}\n\nfunction areCollinear(p1, p2, p3) {\n return crossProduct(p1, p2, p3) === 0;\n}\n\nfunction triangleArea(p1, p2, p3) {\n const area2 = Math.abs(\n p1[0] * (p2[1] - p3[1])\n + p2[0] * (p3[1] - p1[1])\n + p3[0] * (p1[1] - p2[1])\n );\n return area2 / 2.0;\n}\n```\n\n\n### TypeScript\n\n\n```typescript\nfunction euclideanDistance(x1: number, y1: number, x2: number, y2: number): number {\n const dx = x2 - x1;\n const dy = y2 - y1;\n return Math.sqrt(dx * dx + dy * dy);\n}\n\nfunction manhattanDistance(x1: number, y1: number, x2: number, y2: number): number {\n return Math.abs(x2 - x1) + Math.abs(y2 - y1);\n}\n\n// Returns positive for CCW, negative for CW, zero for collinear\nfunction crossProduct(p1: number[], p2: number[], p3: number[]): number {\n return (p2[0] - p1[0]) * (p3[1] - p1[1])\n - (p2[1] - p1[1]) * (p3[0] - p1[0]);\n}\n\n// 0 = collinear, 1 = clockwise, 2 = counterclockwise\nfunction orientation(p1: number[], p2: number[], p3: number[]): number {\n const cross = crossProduct(p1, p2, p3);\n if (cross === 0) return 0;\n return cross > 0 ? 2 : 1;\n}\n\nfunction areCollinear(p1: number[], p2: number[], p3: number[]): boolean {\n return crossProduct(p1, p2, p3) === 0;\n}\n\nfunction triangleArea(p1: number[], p2: number[], p3: number[]): number {\n const area2 = Math.abs(\n p1[0] * (p2[1] - p3[1])\n + p2[0] * (p3[1] - p1[1])\n + p3[0] * (p1[1] - p2[1])\n );\n return area2 / 2.0;\n}\n```\n\n\n---\n\n## Complexity Analysis\n\n\n| Operation | Time Complexity | Space Complexity |\n|-----------|----------------|-----------------|\n| Euclidean distance | O(1) | O(1) |\n| Manhattan distance | O(1) | O(1) |\n| Cross product / Orientation | O(1) | O(1) |\n| Collinearity check | O(1) | O(1) |\n| Triangle area | O(1) | O(1) |\n| Line segment intersection | O(1) | O(1) |\n| Convex hull (Andrew's) | O(n log n) | O(n) |\n| Closest pair of points | O(n log n) | O(n) |\n\n\nAll the basic geometric primitives run in constant time. They are building blocks. The interesting complexity comes when you use these primitives inside larger algorithms. Convex hull is dominated by the initial sort. The closest pair algorithm uses divide and conquer, similar to merge sort, achieving O(n log n) by splitting points along the x-axis and cleverly limiting the cross-boundary comparisons.\n\n---\n\n## Common Mistakes\n\n### 1. Using Floating Point Slopes Instead of Cross Products\n\nThis is the most common mistake in geometry problems. When checking if points are collinear or computing slopes, developers reach for `slope = (y2 - y1) / (x2 - x1)`. This breaks in two ways: division by zero when x1 == x2 (vertical line), and floating point precision errors when comparing slopes.\n\n**The fix:** Always use cross products for collinearity and orientation. The cross product uses only multiplication and subtraction, so it stays in integer arithmetic when your coordinates are integers.\n\n### 2. Integer Overflow in Cross Product Calculations\n\nIf coordinates can be up to 10^4, then the cross product involves multiplying differences that can be up to 2 * 10^4, and then multiplying two such values gives up to 4 * 10^8. That fits in a 32-bit integer. But if coordinates go up to 10^9 (which some problems allow), the intermediate products can reach 4 * 10^18, which overflows a 32-bit integer. You need `long` in Java, `long long` in C++, or similar.\n\n**The fix:** Cast to `long` or `long long` before multiplying. This is why all the implementations above use explicit long casts.\n\n### 3. Forgetting the Absolute Value in Area Calculations\n\nThe Shoelace formula gives a signed area. The sign depends on whether the vertices are listed clockwise or counterclockwise. If you forget the absolute value, you might get negative areas, which leads to wrong answers or, worse, answers that happen to pass some test cases but fail others.\n\n**The fix:** Always wrap the result in `abs()` before dividing by 2.\n\n### 4. Not Handling the Collinear Case in Segment Intersection\n\nThe general intersection test checks if orientations differ. But when points are collinear (cross product is zero), the test breaks down. Two collinear segments might overlap, or they might not. You need a separate check for the collinear case that verifies whether one endpoint lies within the bounding box of the other segment.\n\n**The fix:** After detecting collinearity, check if the x and y projections of the segments overlap.\n\n---\n\n## Common Interview Problems\n\nBefore we wrap up, let us briefly look at how these primitives apply to popular interview problems.\n\n**Max Points on a Line:** For each pair of points, determine how many other points are collinear with them. Use the cross product (not slopes) to avoid floating point issues. Represent the direction as a reduced (dx, dy) pair using GCD, and count using a hash map. Time complexity: O(n^2).\n\n**Rectangle Overlap:** Two axis-aligned rectangles overlap if and only if they overlap in both the x-projection and the y-projection. This reduces to checking if two intervals overlap, which is a one-dimensional problem.\n\n**Closest Pair of Points:** Use divide and conquer. Sort by x, split into halves, solve recursively, then check the strip of width 2d around the dividing line (where d is the best distance so far). The strip check is O(n) because each point needs to be compared with at most 7 others in the strip.\n\n\n```mermaid\nflowchart TD\n A[\"All points sorted by x\"]:::primary\n B[\"Split into left and right halves\"]:::teal\n C[\"Solve left half recursively\"]:::orange\n D[\"Solve right half recursively\"]:::orange\n E[\"d = min(left_d, right_d)\"]:::green\n F[\"Check strip of width 2d
around dividing line\"]:::teal\n G[\"Return overall minimum\"]:::green\n\n A --> B\n B --> C\n B --> D\n C --> E\n D --> E\n E --> F\n F --> G\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n**Interview Insight:** For the closest pair problem, the key insight that interviewers look for is why the strip check is O(n) and not O(n^2). The answer is that in a d x 2d rectangle, you can fit at most a constant number of points (at most 8) with pairwise distance at least d. So each point compares with at most 7 others.\n\n---\n\n## Interview Questions\n\n**Q1: How would you check if three points are collinear without using division?**\n\nUse the cross product. Given points P1(x1, y1), P2(x2, y2), P3(x3, y3), compute:\n\n\n```shell\ncross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)\n```\n\n\nIf cross equals zero, the points are collinear. This avoids division entirely, so there is no risk of division by zero with vertical lines and no floating point precision issues. The computation uses only multiplication and subtraction, keeping everything in integer arithmetic when coordinates are integers.\n\n**Q2: What is the difference between Euclidean and Manhattan distance, and when would you use each?**\n\nEuclidean distance measures the straight-line distance between two points: `sqrt((x2-x1)^2 + (y2-y1)^2)`. Manhattan distance measures the distance along axis-aligned paths: `|x2-x1| + |y2-y1|`. Use Euclidean distance for problems involving actual geometric distance (closest pair, circle intersection). Use Manhattan distance for grid-based problems where movement is restricted to horizontal and vertical steps, such as navigating a city grid or problems on a chessboard with rook movement. A useful optimization: when comparing Euclidean distances, compare squared distances to avoid the expensive and imprecise square root.\n\n**Q3: Explain how Andrew's monotone chain algorithm builds a convex hull.**\n\nThe algorithm sorts points by x-coordinate (ties broken by y), then builds the hull in two passes. The lower hull is built left to right: for each new point, while the last two points and the new point make a clockwise turn (cross product is non-positive), remove the last point. This ensures only counterclockwise turns remain. The upper hull is built right to left with the same logic. Finally, the two halves are concatenated. The sorting step is O(n log n) and each point is added and removed at most once across both passes, so the hull construction is O(n). Total time: O(n log n). Total space: O(n) for the output hull.\n\n**Q4: Why is the Shoelace formula useful in competitive programming and interviews?**\n\nThe Shoelace formula computes the area of any simple polygon given its vertex coordinates in O(n) time, using only addition, subtraction, and multiplication. It works for both convex and concave polygons. In interviews, it appears in problems asking for triangle areas (a special case with 3 vertices), checking if a point lies inside a polygon (by comparing the area of sub-triangles), and validating geometric properties. The formula avoids trigonometric functions entirely, making it both fast and numerically stable. The key thing to remember is to take the absolute value of the result, since the sign depends on the vertex ordering.\n\n---\n\n## Summary\n\n- **Euclidean distance** measures straight-line distance. Compare squared distances when possible to avoid floating point issues.\n- **Manhattan distance** measures axis-aligned distance. Use it for grid-based movement problems.\n- The **cross product** is your most important tool. It determines orientation (clockwise, counterclockwise, collinear) without division.\n- **Collinearity** should always be checked with cross products, never with slope comparison.\n- **Line segment intersection** reduces to four orientation checks, plus a bounding box check for the collinear edge case.\n- The **Shoelace formula** computes polygon area in O(n) using only basic arithmetic. Always take the absolute value.\n- **Convex hull** can be computed in O(n log n) with Andrew's monotone chain. The core operation is the cross product check.\n- For the **closest pair** problem, divide and conquer achieves O(n log n). The strip check is efficient because only a constant number of points can exist in the critical region.\n- Always cast to `long` (or equivalent) before multiplying coordinates to avoid integer overflow.\n- Never use floating point slopes. The cross product is almost always the right tool.\n\n---\n\n## References\n\n- [Computational Geometry: Algorithms and Applications](https://www.springer.com/gp/book/9783540779735), de Berg et al., Springer\n- [CP-Algorithms: Geometry](https://cp-algorithms.com/geometry/basic-geometry.html)\n- [LeetCode 149: Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)\n- [LeetCode 587: Erect the Fence (Convex Hull)](https://leetcode.com/problems/erect-the-fence/)\n- [Wikipedia: Shoelace Formula](https://en.wikipedia.org/wiki/Shoelace_formula)","pageType":"dsa"}

Chapter 10: Geometry

Ashish Pratap Singh

Get Premium