Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Geometry Greedy
DSA

Geometry Greedy

Learn how greedy reasoning can be applied to geometric optimization and selection problems.

Geometry problems often look complicated, but many can be solved using a few simple ideas:

  • Sort points
  • Calculate slopes
  • Use cross products

Cross products + greedy wrapping = convex hull in O(n·h). Watch an interior point get excluded:

Convex Hull (Gift Wrapping)

Wrap the outermost points of a set using the gift-wrapping (Jarvis march).

Start at the leftmost point and repeatedly pick the most counterclockwise point relative to the current one (via cross product). Interior points always lose the comparison and are skipped; when you return to the start the hull is closed. O(n·h) where h is the hull size.

GRAPH VISUALIZER
Steps –
P0P1P2P3P4P5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        start = leftmost point
                      
                        2
                        repeat:
                      
                        3
                          next = point most CCW from current
                      
                        4
                            (for all other points p:
                      
                        5
                             cross(cur → p) kept smallest)
                      
                        6
                        until next == start again
  • Track the boundary with a stack

The most important concept in this article is orientation.

Cross product tells us whether three points turn left, right, or stay on the same line.

Focus on recognizing:

“Points” + “Boundary” + “Turn direction” = Convex Hull / Cross Product

Pattern Table

PatternTypical QuestionsTrigger
Convex HullSmallest boundary containing all pointsCross product + stack
Max Points on LineMaximum collinear pointsSlope counting
OrientationLeft/right turnCross product
Line IntersectionDo lines intersect?Orientation tests

Mental Trigger

Cross product → Determine turn → Keep or remove point

1. Generic Cross Product Template (Base)

Before learning Convex Hull, understand this function.

private long cross(int[] a, int[] b, int[] c) {

    return (long) (b[0] - a[0]) * (c[1] - a[1])
         - (long) (b[1] - a[1]) * (c[0] - a[0]);
}
def cross(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))
long long cross(vector<int>& a, vector<int>& b, vector<int>& c) {
    return (long long)(b[0] - a[0]) * (c[1] - a[1])
         - (long long)(b[1] - a[1]) * (c[0] - a[0]);
}
function cross(a, b, c) {
  return (
    (b[0] - a[0]) * (c[1] - a[1]) -
    (b[1] - a[1]) * (c[0] - a[0])
  );
}

The three points are:

A → B → C

The result tells us the direction of the turn.

cross > 0  → Counter-clockwise / left turn
cross < 0  → Clockwise / right turn
cross == 0 → Collinear

Why long?

Coordinates can be large, so int multiplication can overflow.

Use:

long

for the cross product.

Cross product = Know the direction of a turn.

Pattern 1: Convex Hull

Problem Type

Given many points, find the points that form the outer boundary.

Think of stretching a rubber band around all the points.

The points inside the boundary are not part of the hull.

Java Code

public int[][] convexHull(int[][] points) {

    int n = points.length;

    if (n <= 1) {
        return points;
    }

    // Find the lowest point.
    // If tied, choose the leftmost point.
    int start = 0;

    for (int i = 1; i < n; i++) {

        if (points[i][1] < points[start][1] ||
            (points[i][1] == points[start][1] &&
             points[i][0] < points[start][0])) {

            start = i;
        }
    }

    swap(points, 0, start);

    int[] anchor = points[0];

    // Sort by polar angle from anchor.
    Arrays.sort(points, 1, n, (a, b) -> {

        long cross = cross(anchor, a, b);

        if (cross == 0) {
            long da = distanceSquared(anchor, a);
            long db = distanceSquared(anchor, b);

            return Long.compare(da, db);
        }

        return cross > 0 ? -1 : 1;
    });

    Stack<int[]> stack = new Stack<>();

    stack.push(points[0]);
    stack.push(points[1]);

    for (int i = 2; i < n; i++) {

        while (stack.size() >= 2) {

            int[] b = stack.pop();
            int[] a = stack.peek();

            long turn = cross(a, b, points[i]);

            if (turn > 0) {
                stack.push(b);
                break;
            }
        }

        stack.push(points[i]);
    }

    return stack.toArray(new int[stack.size()][]);
}

private long cross(int[] a, int[] b, int[] c) {

    return (long) (b[0] - a[0]) * (c[1] - a[1])
         - (long) (b[1] - a[1]) * (c[0] - a[0]);
}

private long distanceSquared(int[] a, int[] b) {

    long dx = b[0] - a[0];
    long dy = b[1] - a[1];

    return dx * dx + dy * dy;
}

private void swap(int[][] points, int i, int j) {

    int[] temp = points[i];
    points[i] = points[j];
    points[j] = temp;
}
from functools import cmp_to_key

def convex_hull(points):
    n = len(points)

    if n <= 1:
        return points

    # Find the lowest point.
    # If tied, choose the leftmost point.
    start = 0

    for i in range(1, n):
        if (points[i][1] < points[start][1] or
                (points[i][1] == points[start][1] and
                 points[i][0] < points[start][0])):
            start = i

    points[0], points[start] = points[start], points[0]

    anchor = points[0]

    def distance_squared(a, b):
        dx = b[0] - a[0]
        dy = b[1] - a[1]

        return dx * dx + dy * dy

    def compare(a, b):
        turn = cross(anchor, a, b)

        if turn == 0:
            da = distance_squared(anchor, a)
            db = distance_squared(anchor, b)

            return da - db

        return -1 if turn > 0 else 1

    # Sort by polar angle from anchor.
    points[1:] = sorted(points[1:], key=cmp_to_key(compare))

    stack = [points[0], points[1]]

    for i in range(2, n):
        while len(stack) >= 2:
            b = stack.pop()
            a = stack[-1]

            turn = cross(a, b, points[i])

            if turn > 0:
                stack.append(b)
                break

        stack.append(points[i])

    return stack

def cross(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))
vector<vector<int>> convexHull(vector<vector<int>>& points) {
    int n = points.size();

    if (n <= 1) {
        return points;
    }

    // Find the lowest point.
    // If tied, choose the leftmost point.
    int start = 0;

    for (int i = 1; i < n; i++) {
        if (points[i][1] < points[start][1] ||
            (points[i][1] == points[start][1] &&
             points[i][0] < points[start][0])) {
            start = i;
        }
    }

    swap(points[0], points[start]);

    vector<int> anchor = points[0];

    // Sort by polar angle from anchor.
    sort(points.begin() + 1, points.end(),
         [&](const vector<int>& a, const vector<int>& b) {
             long long turn = cross(anchor, a, b);

             if (turn == 0) {
                 return distanceSquared(anchor, a) <
                        distanceSquared(anchor, b);
             }

             return turn > 0;
         });

    vector<vector<int>> hull;

    hull.push_back(points[0]);
    hull.push_back(points[1]);

    for (int i = 2; i < n; i++) {
        while (hull.size() >= 2) {
            vector<int> b = hull.back();
            hull.pop_back();
            vector<int> a = hull.back();

            long long turn = cross(a, b, points[i]);

            if (turn > 0) {
                hull.push_back(b);
                break;
            }
        }

        hull.push_back(points[i]);
    }

    return hull;
}

long long cross(vector<int>& a, vector<int>& b, vector<int>& c) {
    return (long long)(b[0] - a[0]) * (c[1] - a[1])
         - (long long)(b[1] - a[1]) * (c[0] - a[0]);
}

long long distanceSquared(vector<int>& a, vector<int>& b) {
    long long dx = b[0] - a[0];
    long long dy = b[1] - a[1];

    return dx * dx + dy * dy;
}
function convexHull(points) {
  const n = points.length;

  if (n <= 1) {
    return points;
  }

  // Find the lowest point.
  // If tied, choose the leftmost point.
  let start = 0;

  for (let i = 1; i < n; i++) {
    if (
      points[i][1] < points[start][1] ||
      (points[i][1] === points[start][1] &&
        points[i][0] < points[start][0])
    ) {
      start = i;
    }
  }

  [points[0], points[start]] = [points[start], points[0]];

  const anchor = points[0];

  function distanceSquared(a, b) {
    const dx = b[0] - a[0];
    const dy = b[1] - a[1];

    return dx * dx + dy * dy;
  }

  // Sort by polar angle from anchor.
  const rest = points.slice(1).sort((a, b) => {
    const turn = cross(anchor, a, b);

    if (turn === 0) {
      return distanceSquared(anchor, a) - distanceSquared(anchor, b);
    }

    return turn > 0 ? -1 : 1;
  });

  const ordered = [anchor, ...rest];

  const stack = [];

  stack.push(ordered[0]);
  stack.push(ordered[1]);

  for (let i = 2; i < n; i++) {
    while (stack.length >= 2) {
      const b = stack.pop();
      const a = stack[stack.length - 1];

      const turn = cross(a, b, ordered[i]);

      if (turn > 0) {
        stack.push(b);
        break;
      }
    }

    stack.push(ordered[i]);
  }

  return stack;
}

function cross(a, b, c) {
  return (
    (b[0] - a[0]) * (c[1] - a[1]) -
    (b[1] - a[1]) * (c[0] - a[0])
  );
}

What Changed from the Base Cross Product?

1. Find an anchor point

Added:

int start = 0;

for (int i = 1; i < n; i++) {
    ...
}

We choose the lowest point as the starting point.

Why?

It gives us a fixed point from which we can sort the other points by angle.

2. Sort points by angle

Added:

Arrays.sort(points, 1, n, ...);

Now points are processed around the anchor.

Convex Hull = Choose anchor + Sort by angle.

3. Use a stack

Added:

Stack<int[]> stack = new Stack<>();

The stack stores the current boundary.

4. Remove points that create a wrong turn

Added:

while (stack.size() >= 2) {

    ...

    if (turn > 0) {
        ...
        break;
    }
}

If three points make a clockwise turn:

A → B → C

then B cannot be part of the convex boundary.

So we remove it.

Wrong turn → Remove middle point → Continue.

Pattern 2: Max Points on a Line

Problem Type

Instead of finding the outside boundary, we want:

“What is the maximum number of points lying on the same straight line?”

For every point, calculate the slope to every other point.

Points with the same slope are on the same line.

Java Code

public int maxPoints(int[][] points) {

    int n = points.length;

    if (n <= 2) {
        return n;
    }

    int max = 1;

    for (int i = 0; i < n; i++) {

        Map<String, Integer> slopes = new HashMap<>();

        for (int j = i + 1; j < n; j++) {

            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];

            int gcd = gcd(dx, dy);

            dx /= gcd;
            dy /= gcd;

            // Keep one consistent representation.
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }

            if (dx == 0) {
                dy = 1;
            }

            if (dy == 0) {
                dx = 1;
            }

            String slope = dx + "#" + dy;

            int count = slopes.getOrDefault(slope, 0) + 1;

            slopes.put(slope, count);

            max = Math.max(max, count + 1);
        }
    }

    return max;
}

private int gcd(int a, int b) {

    a = Math.abs(a);
    b = Math.abs(b);

    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}
def max_points(points):
    n = len(points)

    if n <= 2:
        return n

    best = 1

    for i in range(n):
        slopes = {}

        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]

            g = gcd(dx, dy)

            dx //= g
            dy //= g

            # Keep one consistent representation.
            if dx < 0:
                dx = -dx
                dy = -dy

            if dx == 0:
                dy = 1

            if dy == 0:
                dx = 1

            slope = f"{dx}#{dy}"

            count = slopes.get(slope, 0) + 1

            slopes[slope] = count

            best = max(best, count + 1)

    return best

def gcd(a, b):
    a = abs(a)
    b = abs(b)

    while b != 0:
        a, b = b, a % b

    return a
int maxPoints(vector<vector<int>>& points) {
    int n = points.size();

    if (n <= 2) {
        return n;
    }

    int best = 1;

    for (int i = 0; i < n; i++) {
        unordered_map<string, int> slopes;

        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];

            int g = gcdOf(dx, dy);

            dx /= g;
            dy /= g;

            // Keep one consistent representation.
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }

            if (dx == 0) {
                dy = 1;
            }

            if (dy == 0) {
                dx = 1;
            }

            string slope = to_string(dx) + "#" + to_string(dy);

            int count = ++slopes[slope];

            best = max(best, count + 1);
        }
    }

    return best;
}

int gcdOf(int a, int b) {
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}
function maxPoints(points) {
  const n = points.length;

  if (n <= 2) {
    return n;
  }

  let max = 1;

  for (let i = 0; i < n; i++) {
    const slopes = new Map();

    for (let j = i + 1; j < n; j++) {
      let dx = points[j][0] - points[i][0];
      let dy = points[j][1] - points[i][1];

      const g = gcd(dx, dy);

      dx /= g;
      dy /= g;

      // Keep one consistent representation.
      if (dx < 0) {
        dx = -dx;
        dy = -dy;
      }

      if (dx === 0) {
        dy = 1;
      }

      if (dy === 0) {
        dx = 1;
      }

      const slope = `${dx}#${dy}`;

      const count = (slopes.get(slope) || 0) + 1;

      slopes.set(slope, count);

      max = Math.max(max, count + 1);
    }
  }

  return max;
}

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);

  while (b !== 0) {
    const temp = a % b;
    a = b;
    b = temp;
  }

  return a;
}

What Changed from Convex Hull?

1. No sorting

Convex Hull:

Arrays.sort(...)

Changed to:

Map<String, Integer> slopes = new HashMap<>();

because we are not interested in the boundary.

We only need to group points having the same direction.

2. No stack

Convex Hull:

Stack<int[]> stack

Removed.

Instead, we count:

slopes.put(slope, count);

because the problem asks:

How many points share the same line?

3. Calculate slope

Added:

int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];

and normalize the direction using gcd.

This avoids problems such as:

2/4
1/2

representing the same slope.

Max Points on Line = Fix one point + Normalize slopes + Count.

Pattern 3: Orientation Check

This is one of the most useful geometry building blocks.

Java Code

private long orientation(int[] a, int[] b, int[] c) {

    return (long) (b[0] - a[0]) * (c[1] - a[1])
         - (long) (b[1] - a[1]) * (c[0] - a[0]);
}
def orientation(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))
long long orientation(vector<int>& a, vector<int>& b, vector<int>& c) {
    return (long long)(b[0] - a[0]) * (c[1] - a[1])
         - (long long)(b[1] - a[1]) * (c[0] - a[0]);
}
function orientation(a, b, c) {
  return (
    (b[0] - a[0]) * (c[1] - a[1]) -
    (b[1] - a[1]) * (c[0] - a[0])
  );
}

What Changed from the Base?

Nothing.

Orientation is the cross product.

Use:

orientation(a, b, c)

to determine whether:

A → B → C

turns left, right, or stays straight.

Orientation = Cross product used as a turn detector.

Pattern 4: Line Segment Intersection

Problem Type

Determine whether two line segments intersect.

Suppose we have:

A -------- B
     ×
C -------- D

We can compare the orientations of the four point combinations.

Java Code

public boolean intersects(
        int[] a,
        int[] b,
        int[] c,
        int[] d) {

    long o1 = orientation(a, b, c);
    long o2 = orientation(a, b, d);
    long o3 = orientation(c, d, a);
    long o4 = orientation(c, d, b);

    // General intersection
    if (((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0)) &&
        ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0))) {

        return true;
    }

    // Collinear cases
    if (o1 == 0 && onSegment(a, b, c)) return true;
    if (o2 == 0 && onSegment(a, b, d)) return true;
    if (o3 == 0 && onSegment(c, d, a)) return true;
    if (o4 == 0 && onSegment(c, d, b)) return true;

    return false;
}

private long orientation(int[] a, int[] b, int[] c) {

    return (long) (b[0] - a[0]) * (c[1] - a[1])
         - (long) (b[1] - a[1]) * (c[0] - a[0]);
}

private boolean onSegment(
        int[] a,
        int[] b,
        int[] p) {

    return p[0] >= Math.min(a[0], b[0]) &&
           p[0] <= Math.max(a[0], b[0]) &&
           p[1] >= Math.min(a[1], b[1]) &&
           p[1] <= Math.max(a[1], b[1]);
}
def intersects(a, b, c, d):
    o1 = orientation(a, b, c)
    o2 = orientation(a, b, d)
    o3 = orientation(c, d, a)
    o4 = orientation(c, d, b)

    # General intersection
    if (((o1 > 0 and o2 < 0) or (o1 < 0 and o2 > 0)) and
            ((o3 > 0 and o4 < 0) or (o3 < 0 and o4 > 0))):
        return True

    # Collinear cases
    if o1 == 0 and on_segment(a, b, c):
        return True
    if o2 == 0 and on_segment(a, b, d):
        return True
    if o3 == 0 and on_segment(c, d, a):
        return True
    if o4 == 0 and on_segment(c, d, b):
        return True

    return False

def orientation(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))

def on_segment(a, b, p):
    return (p[0] >= min(a[0], b[0]) and
            p[0] <= max(a[0], b[0]) and
            p[1] >= min(a[1], b[1]) and
            p[1] <= max(a[1], b[1]))
bool intersects(vector<int>& a, vector<int>& b,
                vector<int>& c, vector<int>& d) {
    long long o1 = orientation(a, b, c);
    long long o2 = orientation(a, b, d);
    long long o3 = orientation(c, d, a);
    long long o4 = orientation(c, d, b);

    // General intersection
    if (((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0)) &&
        ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0))) {
        return true;
    }

    // Collinear cases
    if (o1 == 0 && onSegment(a, b, c)) return true;
    if (o2 == 0 && onSegment(a, b, d)) return true;
    if (o3 == 0 && onSegment(c, d, a)) return true;
    if (o4 == 0 && onSegment(c, d, b)) return true;

    return false;
}

long long orientation(vector<int>& a, vector<int>& b, vector<int>& c) {
    return (long long)(b[0] - a[0]) * (c[1] - a[1])
         - (long long)(b[1] - a[1]) * (c[0] - a[0]);
}

bool onSegment(vector<int>& a, vector<int>& b, vector<int>& p) {
    return p[0] >= min(a[0], b[0]) &&
           p[0] <= max(a[0], b[0]) &&
           p[1] >= min(a[1], b[1]) &&
           p[1] <= max(a[1], b[1]);
}
function intersects(a, b, c, d) {
  const o1 = orientation(a, b, c);
  const o2 = orientation(a, b, d);
  const o3 = orientation(c, d, a);
  const o4 = orientation(c, d, b);

  // General intersection
  if (
    ((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0)) &&
    ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0))
  ) {
    return true;
  }

  // Collinear cases
  if (o1 === 0 && onSegment(a, b, c)) return true;
  if (o2 === 0 && onSegment(a, b, d)) return true;
  if (o3 === 0 && onSegment(c, d, a)) return true;
  if (o4 === 0 && onSegment(c, d, b)) return true;

  return false;
}

function orientation(a, b, c) {
  return (
    (b[0] - a[0]) * (c[1] - a[1]) -
    (b[1] - a[1]) * (c[0] - a[0])
  );
}

function onSegment(a, b, p) {
  return (
    p[0] >= Math.min(a[0], b[0]) &&
    p[0] <= Math.max(a[0], b[0]) &&
    p[1] >= Math.min(a[1], b[1]) &&
    p[1] <= Math.max(a[1], b[1])
  );
}

What Changed from Orientation?

1. Calculate four orientations

Added:

long o1 = orientation(a, b, c);
long o2 = orientation(a, b, d);
long o3 = orientation(c, d, a);
long o4 = orientation(c, d, b);

We check how each endpoint sits relative to the opposite segment.

2. Check opposite sides

Added:

(o1 > 0 && o2 < 0) ||
(o1 < 0 && o2 > 0)

If two endpoints are on opposite sides of a line, the segments may intersect.

3. Handle collinear points

Added:

if (o1 == 0 && onSegment(a, b, c))

because two segments can touch even when all relevant points are on the same line.

Line Intersection = Orientation checks + Collinear boundary checks.

Geometry Pattern Evolution

Cross Product
    ↓
Orientation
    (+ left / right / collinear)
    ↓
Convex Hull
    (+ sort by angle + stack)
    ↓
Line Intersection
    (+ four orientation checks)


Separate Pattern:
Max Points on Line
    ↓
Fix one point
    ↓
Calculate normalized slopes
    ↓
Count equal slopes

Common Mistakes

1. Using int for Cross Product

Risky:

int cross = ...

Use:

long cross = ...

because multiplication can overflow int.

2. Using Floating Point Slopes

This can cause precision problems:

double slope = (double) dy / dx;

For exact geometry problems, prefer:

dy / gcd(dy, dx)

and store the normalized integer pair.

3. Forgetting Vertical Lines

A vertical line has:

dx = 0

Normalize it separately instead of dividing by zero.

4. Forgetting Collinear Cases

For line intersection, this is not enough:

o1 * o2 < 0

You also need to handle:

o == 0

when points are collinear.

5. Removing the Wrong Point in Convex Hull

The key check is:

cross(a, b, c)

where:

a = second-last point
b = last point
c = current point

If the turn is not allowed, remove b.

Recognition Cheat Sheet

If you see…Think…
Smallest boundary around pointsConvex Hull
Outer points / polygon boundaryConvex Hull
Left/right turnCross Product
Three points orientationCross Product
Maximum points on one lineSlope Counting
Collinear pointsNormalized Slope
Line segments intersectOrientation
Clockwise / counter-clockwiseCross Product

My Private Notes

Notes are auto-saved locally to this device.