Get started

Geometry Coding Problems: 7 Questions with Solutions

7 geometry coding problems — 3 easy · 3 medium · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 4-day plan.

  • Problems: 7
  • By difficulty: 3 easy · 3 medium · 1 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Geometry problems put points, lines and shapes on a plane, usually with integer coordinates: are these points on one line, which are closest to the origin, how many lie on the best line, what is the smallest rectangle their corners make. The ideas are short — slopes, cross products, squared distances, the diagonal moves of a king — and the difficulty is exactness. The problems here practise keeping every comparison in integers, so that no rounding decides what the coordinates settle exactly.

How geometry works, step by step

ABCDEFGhull: A B D G F CO(n log n) for the sort, O(n) for the chainslowerupperABDGGFCA
Convex hull of a point set, with Andrew's monotone chain. Example: points = (3, 0), (0, 2), (5, 3), (2, 4), (6, 1), (1, 0), (4, 3)
  1. Sort the points by x and name them A to G in that order. Andrew's monotone chain builds the lower hull left to right and the upper hull right to left, keeping only left turns; the sign of a cross product tells which way a turn goes.
  2. Adding C: A → B → C turns counter-clockwise (cross = 6), so B stays and C joins. A counter-clockwise turn keeps the chain bending one way, which is what convex means.
  3. Adding D: B → C → D turns clockwise (cross = −8), so C is popped; A → B → D turns counter-clockwise (cross = 4), so B stays and D joins. A clockwise turn means C lies on the inner side of the segment BD, so it cannot be a corner of the hull.
  4. Adding E: B → D → E turns counter-clockwise (cross = 6), so D stays and E joins.
  5. Adding F: D → E → F turns clockwise (cross = −3), so E is popped; B → D → F turns counter-clockwise (cross = 6), so D stays and F joins.
  6. Adding G: D → F → G turns clockwise (cross = −7), so F is popped; B → D → G turns counter-clockwise (cross = 2), so D stays and G joins.
  7. The lower hull A → B → D → G is done; the upper pass restarts from G and F. Adding E: G → F → E turns counter-clockwise (cross = 2), so F stays and E joins.
  8. Adding D: F → E → D turns counter-clockwise (cross = 3), so E stays and D joins.
  9. Adding C: E → D → C turns clockwise (cross = −7), so D is popped; F → E → C turns clockwise (cross = −1), so E is popped; G → F → C turns counter-clockwise (cross = 5), so F stays and C joins.
  10. Adding B: F → C → B turns counter-clockwise (cross = 13), so C stays and B joins.
  11. Adding A: C → B → A turns clockwise (cross = −6), so B is popped; F → C → A turns counter-clockwise (cross = 8), so C stays and A joins.
  12. The hull is A → B → D → G → F → C: the lower chain plus the upper one, which share the end points. E lies inside. Sorting costs O(n log n); each point is pushed and popped at most once per chain, so the scan itself is O(n).

Geometry study plan

All 7 Geometry problems (3 easy, 3 medium and 1 hard) over 4 days, about 3 h 50 min in all — the pattern first, then easiest to hardest. Then move on to Brainteaser.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Next topic: Brainteaser

Geometry: the essentials

When to reach for it

Points as [x, y], circles as [x, y, r], rectangles or heights on a grid, with a question about collinearity, distance, area or containment. Integer coordinates, up to 10⁴ or 10⁹, say that the exact answer needs no floating point.

The pattern

Replace division and square roots with multiplication. Three points are collinear when the cross product of b - a and c - a is zero — no slope, no vertical special case — and its sign tells a left turn from a right. Compare distances by their squares: dx² + dy² ranks points as the distance does, and a point is inside or on a circle when dx² + dy² ≤ r². To group points by slope, reduce the direction by its gcd, fix its sign and use it as a Hash Table key.

from math import gcd

def cross(o, a, b):                 # > 0 left turn, < 0 right turn, 0 collinear
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def direction(p, q):                # slope from p to q as an exact key, p != q
    dx, dy = q[0] - p[0], q[1] - p[1]
    g = gcd(dx, dy)
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):
        dx, dy = -dx, -dy           # one sign, so p→q and q→p agree
    return dx, dy

Cost

Every pair of points is O(n²); with a map of directions per anchor point, Max Points on a Line is O(n²) time and O(n) space.

Common mistakes

  • Floating-point slopes: dy / dx fails on vertical lines, close slopes can round alike, and Java's Double keys tell 0.0 from −0.0.
  • Overflow: with coordinates up to 10⁹, a cross product or squared distance reaches about 10¹⁸; use 64-bit integers.
  • Duplicate points have no direction between them; count them apart and add them to every line through that point.
  • Reading "inside or on" as <: a point on the boundary satisfies <=.

Start with

All geometry problems

Easy (3)

Medium (3)

Hard (1)

Companies that ask geometry problems

Next topic: Brainteaser