Geometry problem set

Why this matters when you build with AI

An AI tool can write geometry code that passes the sample and fails on the first degenerate input. A degenerate input has no area or no clear turn: two equal points, three points on one line, a polygon with all points collinear. The sample rarely contains these cases, so the bug shows up only in the judge's data.

Two real symptoms from my scratch runs show the pattern. First, a float cross product gave the wrong turn for three points with coordinates near 10^9. The exact value is -1, which is a right turn, and the float value is 0.0, which means the points are on one line:

exact -1 float 0.0

Second, a convex hull that keeps points on its edges reports a different count from one that does not. For the points (0, 0), (2, 0), (4, 0), (4, 4) and (0, 4), the strict hull has 4 corners and the hull that keeps collinear points has 5 vertices. Which one is right depends on the problem statement, and a tool that does not read the statement will pick one at random.

This set has twelve problems. Each one needs one of the predicates from the module: an orientation sign, a dot product sign, an exact squared distance, a Manhattan-to-Chebyshev transform, a reflection, or an in-circle determinant. Each problem has an answer key that I ran on small random inputs and compared with an independent brute force. Solve them in any order.

How to work this set

Use the same five steps on every problem.

Name the predicate the statement needs. Write it in words before any code, for example "sign of the cross product of ab and ac".
Write the brute force first. It can be O(n^2) or O(n^3) and must be simple enough that you trust it.
Check the largest value your formula can reach. If it can pass 9 * 10^18, use 128-bit integers in C++ (__int128), or Python integers.
Run the sample, then your brute force on at least 200 random small inputs with edge values: repeated points, collinear points, zero vectors, and points on a circle.
Write one line for the note at the end: the problem number, the predicate and the edge case that decided the answer.

The answer keys below use a few shared helpers. cross(o, a, b) returns (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x), which is positive for a left turn. hull_strict(points, keep_collinear) is the monotone chain from lesson 05, and it drops points that lie on an edge unless keep_collinear is true.

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
 
def hull_strict(pts, keep_collinear=False):
    pts = sorted(set(pts))
    if len(pts) <= 1:
        return pts
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and (cross(lower[-2], lower[-1], p) < 0 if keep_collinear else cross(lower[-2], lower[-1], p) <= 0):
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and (cross(upper[-2], upper[-1], p) < 0 if keep_collinear else cross(upper[-2], upper[-1], p) <= 0):
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

Each answer key is a function that takes the list of all input integers and returns the output lines. The driver below reads stdin, runs the key for problem 4 and prints its lines. For another problem, change p4 to that problem's key name.

import sys
 
data = list(map(int, sys.stdin.read().split()))
print("\n".join(p4(data)))

The problems

Problem 1: Turn direction

Given T triples of points a, b, c, walk from a to b and then from b to c. Print LEFT if the second step turns counterclockwise, RIGHT if it turns clockwise, and STRAIGHT if the three points lie on one line. Repeated points count as STRAIGHT.

Input: T (1 to 100000), then T lines of six integers x1 y1 x2 y2 x3 y3. All values have absolute value at most 10^9. Output: one word per line.

Sample input:

4
0 0 1 0 1 1
0 0 1 0 2 0
0 0 1 0 1 -1
5 5 5 5 1 2

Sample output:

LEFT
STRAIGHT
RIGHT
STRAIGHT

Edge hints: a equal to b gives STRAIGHT. With values near 10^9, each difference is at most 2 * 10^9 and each product at most 4 * 10^18, so the result fits in a signed 64-bit integer. Floating point is the wrong tool here, as the symptom above shows.

Show the answer

The predicate is the sign of cross(a, b, c). The key below uses it directly. The output is LEFT when the value is positive, RIGHT when it is negative, and STRAIGHT when it is zero.

def p1(data):
    t = data[0]; out = []
    for i in range(t):
        x1, y1, x2, y2, x3, y3 = data[1 + 6 * i: 7 + 6 * i]
        c = cross((x1, y1), (x2, y2), (x3, y3))
        out.append("LEFT" if c > 0 else "RIGHT" if c < 0 else "STRAIGHT")
    return out

Problem 2: Corner type

Given T pairs of vectors u = (ax, ay) and v = (bx, by), print ZERO if either vector is the zero vector. Otherwise print ACUTE if the angle between them is less than 90 degrees, RIGHT if it is exactly 90 degrees, and OBTUSE if it is more than 90 degrees.

Input: T (1 to 100000), then T lines of four integers ax ay bx by. All values have absolute value at most 10^9. Output: one word per line.

Sample input:

Sample output:

RIGHT
ACUTE
OBTUSE
ZERO

Edge hints: two vectors in the same direction with different lengths give ACUTE. Two vectors pointing opposite ways give OBTUSE, with an angle of 180 degrees. A zero vector gives ZERO even when the other vector is also zero. Each product is at most 10^18, so the dot product fits in a signed 64-bit integer.

Show the answer

The sign of the dot product decides the case, because the dot product is positive for an acute angle, zero for a right angle and negative for an obtuse one. Using the arc cosine would need a floating point comparison at exactly 90 degrees, and a float can miss an exact right angle. The key checks the zero vectors first.

def p2(data):
    t = data[0]; out = []
    for i in range(t):
        ax, ay, bx, by = data[1 + 4 * i: 5 + 4 * i]
        if (ax, ay) == (0, 0) or (bx, by) == (0, 0):
            out.append("ZERO"); continue
        d = ax * bx + ay * by
        out.append("ACUTE" if d > 0 else "RIGHT" if d == 0 else "OBTUSE")
    return out

Problem 3: Winding area

Given a simple polygon with n vertices listed in order around its boundary (simple means its edges do not cross or touch except at shared endpoints), print twice its area as an integer, then the word CCW if the vertices are in counterclockwise order and CW if they are clockwise.

Input: n (3 to 200000), then n lines x y. All values have absolute value at most 10^9. Output: one line with two items.

Sample input:

4
0 0 2 0 2 2 0 2

Sample output:

8 CCW

Edge hints: a triangle is the smallest case. Print twice the area, not the area, so the output is always an integer. Each term x_i * y_{i+1} - x_{i+1} * y_i can reach 2 * 10^18, and the sum of up to 200000 terms can reach about 4 * 10^23. That is past the signed 64-bit limit, so use 128-bit integers in C++.

Show the answer

Use the shoelace formula. The sum of x_i * y_{i+1} - x_{i+1} * y_i over the edges is twice the signed area. A positive sum means counterclockwise order. The key uses Python integers, which do not overflow.

def p3(data):
    n = data[0]
    P = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
    s = 0
    for i in range(n):
        x1, y1 = P[i]; x2, y2 = P[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return [f"{abs(s)} {'CCW' if s > 0 else 'CW'}"]

Problem 4: Convex polygon and query points

Given a strictly convex polygon with n vertices in counterclockwise order (no three vertices on one line), and q query points, print IN if a query is strictly inside, ON if it lies on an edge or is a vertex, and OUT otherwise.

Input: n (3 to 1000), then n vertices x y, then q (1 to 1000), then q points x y. All values have absolute value at most 10^6. Output: one word per line.

Sample input:

4
0 0 4 0 4 4 0 4
5
2 2
0 0
4 2
5 5
0 4

Sample output:

IN
ON
ON
OUT
ON

Edge hints: a query on the line through an edge but beyond the end of that edge is OUT. Check the segment bounds, not only the line. A vertex is ON. The sample has a query at (4, 2), which is in the middle of an edge, and a query at (0, 4), which is a vertex.

Show the answer

For each edge, compute the cross product of the edge with the query point. If any value is negative, the point is outside. If every value is at least zero and one value is zero, the point is on the boundary, but only when it is inside the bounds of that edge. This check is O(n) per query, which is fast enough for these limits.

def p4(data):
    n = data[0]
    P = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
    k = 1 + 2 * n
    q = data[k]
    out = []
    for i in range(q):
        x, y = data[k + 1 + 2 * i], data[k + 2 + 2 * i]
        on = False; inside = True
        for j in range(n):
            c = cross(P[j], P[(j + 1) % n], (x, y))
            if c < 0:
                inside = False
            if c == 0:
                a, b = P[j], P[(j + 1) % n]
                if min(a[0], b[0]) <= x <= max(a[0], b[0]) and min(a[1], b[1]) <= y <= max(a[1], b[1]):
                    on = True
        out.append("ON" if on and inside else "IN" if inside else "OUT")
    return out

Problem 5: Touching segments

Given n segments, each with two endpoints, count the pairs i < j whose segments share at least one point. Sharing includes crossing, touching at an endpoint and overlapping along one line. A segment may be a single point. Two identical segments share points.

Input: n (1 to 2000), then n lines x1 y1 x2 y2. All values have absolute value at most 10^6. Output: one integer.

Sample input:

Sample output:

Edge hints: the sample has a touching pair at (6, 6) and a crossing pair at (1, 1). A segment that is a single point is a valid input. Collinear segments may overlap without crossing, so do not test only for a proper crossing.

Show the answer

Use the standard test. Two segments share a point when they cross properly (the endpoints of each lie strictly on opposite sides of the other), or when an endpoint of one lies on the other. The key uses the cross product for every side test and checks the endpoints separately, so touching and collinear cases are covered. The pair loop is O(n^2), which is enough for n up to 2000.

def p5(data):
    n = data[0]
    S = [((data[1 + 4 * i], data[2 + 4 * i]), (data[3 + 4 * i], data[4 + 4 * i])) for i in range(n)]
    def onseg(p, a, b):
        return cross(a, b, p) == 0 and min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1])
    def inter(s, t):
        a, b = s; c, d = t
        d1, d2 = cross(a, b, c), cross(a, b, d)
        d3, d4 = cross(c, d, a), cross(c, d, b)
        if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
            return True
        return onseg(c, a, b) or onseg(d, a, b) or onseg(a, c, d) or onseg(b, c, d)
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            if inter(S[i], S[j]):
                cnt += 1
    return [str(cnt)]

Problem 6: Fence

Given n points (repeats allowed), let D be the set of distinct points. Print two integers: the number of corners of the convex hull of D, and the number of points of D on the boundary of the hull, corners included.

A corner is a point where the boundary turns. A single point has one corner. A segment has two corners, its endpoints. A point in the middle of an edge is on the boundary but is not a corner.

Input: n (1 to 2000), then n lines x y. All values have absolute value at most 10^6. Output: one line with two integers.

Sample input:

Sample output:

4 5

Edge hints: all points equal gives 1 1. All points on one line give 2 k, where k is the number of distinct points on that segment. Repeated points count once in both numbers. The sample has the point (2, 0) on the bottom edge (a boundary point, not a corner) and a repeated (2, 2) inside the square.

Show the answer

Build the strict hull with the helper, which removes points on edges. The corners are the hull vertices. The boundary count checks each distinct point against each hull edge: a point is on the boundary when it lies on some edge segment. The sample has a strict hull of 4 corners and 5 boundary points. The hull that keeps collinear points has 5 vertices on the same sample, which is the mistake described in the first section.

def p6(data):
    n = data[0]
    P = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
    D = sorted(set(P))
    if len(D) == 1:
        return ["1 1"]
    H = hull_strict(D, keep_collinear=False)
    if len(H) == 2:
        # segment: count distinct points on it (all of them lie on the segment's line between the ends)
        a, b = H
        onb = sum(1 for p in D if cross(a, b, p) == 0)
        return [f"2 {onb}"]
    # polygon: count distinct points on its boundary
    onb = 0
    for p in D:
        on = False
        for j in range(len(H)):
            a, b = H[j], H[(j + 1) % len(H)]
            if cross(a, b, p) == 0 and min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]):
                on = True
        onb += on
    return [f"{len(H)} {onb}"]

Problem 7: Farthest pair

Given n points with n at least 2, print the largest squared distance between two of the points. Repeated points are allowed.

Input: n (2 to 200000), then n lines x y. All values have absolute value at most 10^6. Output: one integer.

Sample input:

Sample output:

Edge hints: all points equal gives 0. The answer is a squared distance, so it stays an integer, and it is at most 8 * 10^12, which fits in a signed 64-bit integer. The farthest pair is always two hull vertices, so the search can skip interior points.

Show the answer

Build the hull, then use rotating calipers. For each hull edge, move a second pointer forward while the vertex it points to is farther from that edge. The pointer never moves backward, which is why the walk takes O(h) time for a hull of h vertices. Check the distance from both ends of the edge to the pointer. The key falls back to the plain distance when the hull has only two points.

def p7(data):
    n = data[0]
    P = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
    H = hull_strict(P, keep_collinear=False)
    if len(H) == 1:
        return ["0"]
    best = 0; m = len(H)
    # rotating calipers over the hull, pointer j moves forward only
    j = 1
    def d2(a, b):
        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
    for i in range(m):
        a, b = H[i], H[(i + 1) % m]
        while cross(a, b, H[(j + 1) % m]) > cross(a, b, H[j % m]):
            j = (j + 1) % m
        best = max(best, d2(a, H[j]), d2(b, H[j]))
    if m == 2:
        best = d2(H[0], H[1])
    return [str(best)]

Problem 8: Closest pair

Given n points with n at least 2, print the smallest squared distance between two different input points. Two points with the same coordinates count as distance zero.

Input: n (2 to 200000), then n lines x y. All values have absolute value at most 10^9. Output: one integer.

Sample input:

Sample output:

Edge hints: a repeated point gives 0. A squared distance can reach 8 * 10^18, which is just inside a signed 64-bit integer (its limit is about 9.2 * 10^18). Sorting by x is enough to find candidate pairs, but the pairs checked must include points near the dividing line, so a second pass over a narrow strip is needed.

Show the answer

Use divide and conquer on the points sorted by x. Solve each half, then check the strip of points within the best distance of the dividing line, sorted by y. In each strip point, only the next few points in y order can be closer than the best distance, so the inner loop stops early. This version re-sorts the strip at each level, so it runs in O(n log^2 n) time. Sorting the halves once would give O(n log n), which is the standard version.

def p8(data):
    n = data[0]
    P = sorted([(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)])
    def rec(lo, hi):
        if hi - lo <= 3:
            best = None
            for i in range(lo, hi):
                for j in range(i + 1, hi):
                    d = (P[i][0] - P[j][0]) ** 2 + (P[i][1] - P[j][1]) ** 2
                    best = d if best is None or d < best else best
            return best
        mid = (lo + hi) // 2
        mx = P[mid][0]
        best = min(rec(lo, mid), rec(mid, hi))
        strip = sorted([P[i] for i in range(lo, hi) if (P[i][0] - mx) ** 2 < best], key=lambda p: p[1])
        for i in range(len(strip)):
            for j in range(i + 1, len(strip)):
                if (strip[j][1] - strip[i][1]) ** 2 >= best:
                    break
                d = (strip[i][0] - strip[j][0]) ** 2 + (strip[i][1] - strip[j][1]) ** 2
                best = min(best, d)
        return best
    return [str(rec(0, n))]

Problem 9: Circle and line

A circle has integer centre (cx, cy) and integer squared radius R2 (1 to 10^12). Then q lines are given, each by two distinct points on it. For each line print 2 if it cuts the circle in two points, 1 if it touches the circle at one point, and 0 if it misses the circle.

Input: cx cy R2, then q (1 to 100000), then q lines x1 y1 x2 y2. All coordinates have absolute value at most 10^6. Output: one digit per line.

Sample input:

Sample output:

2
1
0

Edge hints: compare squares, not distances. The squared distance from the centre to the line is cross^2 / len2, so the comparison is cross^2 against R2 * len2. The cross product can reach about 8 * 10^12, so its square can reach about 6 * 10^25, which needs 128-bit integers in C++. The sample uses the x-axis (distance 0), the line y = 5 (a tangent) and the line x = 6 (a miss).

Show the answer

Let L = len2 and c = cross(p2 - p1, centre - p1). The squared distance from the centre to the line is c^2 / L. Compare c^2 with R2 * L (the answer is 2 if smaller, 1 if equal, 0 if larger). No square root is needed.

def p9(data):
    cx, cy, R2 = data[0], data[1], data[2]
    q = data[3]; out = []
    for i in range(q):
        x1, y1, x2, y2 = data[4 + 4 * i: 8 + 4 * i]
        L2 = (x2 - x1) ** 2 + (y2 - y1) ** 2
        cr = (x2 - x1) * (cy - y1) - (y2 - y1) * (cx - x1)
        lhs, rhs = cr * cr, R2 * L2
        out.append("2" if lhs < rhs else "1" if lhs == rhs else "0")
    return out

Problem 10: Manhattan neighbours

Given n points and an integer D (at least 0), count the pairs i < j whose Manhattan distance is at most D. The Manhattan distance between (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.

Input: n and D on one line (1 to 2000 points, 0 to 10^6 for D), then n lines x y. All coordinates have absolute value at most 10^6. Output: one integer.

Sample input:

Sample output:

Edge hints: D = 0 counts only repeated points. The Manhattan distance is not the Euclidean one, so the circle test does not apply. The sample has the pairs (0, 0) with (1, 2), and (1, 2) with (3, 1).

Show the answer

Rotate every point with (x, y) -> (x + y, x - y). Then |dx| + |dy| becomes max(|du|, |dv|), which is the Chebyshev distance, and the check becomes a simple box test. The key counts pairs in O(n^2) time, which is enough for n up to 2000. For larger n, sorting by one coordinate reduces the work.

def p10(data):
    n, D = data[0], data[1]
    P = [(data[2 + 2 * i], data[3 + 2 * i]) for i in range(n)]
    Q = [(x + y, x - y) for x, y in P]  # Manhattan distance <= D is Chebyshev distance <= D in Q
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            if max(abs(Q[i][0] - Q[j][0]), abs(Q[i][1] - Q[j][1])) <= D:
                cnt += 1
    return [str(cnt)]

Problem 11: Mirror pairs

Given n distinct points S and a line through two distinct integer points a and b, count the points p in S whose mirror image across the line is also in S. A point on the line is its own mirror image, so it counts.

Input: n (1 to 200000), then n lines x y, then one line ax ay bx by. All coordinates have absolute value at most 10^6. Output: one integer.

Sample input:

Sample output:

Edge hints: a mirror image can have fractional coordinates. It only counts when both coordinates are integers and the point is in S. The sample line is the y axis, so (1, 0) and (-1, 0) are mirror images, (0, 2) and (0, -2) are each on the axis, and (3, 3) has no image in S. The intermediate values reach about 3 * 10^19, which needs 128-bit integers in C++.

Show the answer

Let u = b - a, L = u . u, w = p - a and t = w . u. The mirror image multiplied by L is L * a + 2 * t * u - L * w. Check that both coordinates divide by L exactly, then look up the result in S. Working with the numerator keeps every value an integer.

def p11(data):
    n = data[0]
    S = set((data[1 + 2 * i], data[2 + 2 * i]) for i in range(n))
    k = 1 + 2 * n
    ax, ay, bx, by = data[k: k + 4]
    ux, uy = bx - ax, by - ay
    L = ux * ux + uy * uy
    cnt = 0
    for (x, y) in S:
        wx, wy = x - ax, y - ay
        dt = wx * ux + wy * uy
        Nx = L * ax + 2 * dt * ux - L * wx
        Ny = L * ay + 2 * dt * uy - L * wy
        if Nx % L == 0 and Ny % L == 0 and (Nx // L, Ny // L) in S:
            cnt += 1
    return [str(cnt)]

Problem 12: Inside the circumcircle

Given a triangle a, b, c in strictly counterclockwise order, and n points, count the points that lie strictly inside the circle through a, b and c. Points on the circle do not count.

Input: six integers ax ay bx by cx cy, then n (1 to 2000), then n lines x y. All values have absolute value at most 10^6. Output: one integer.

Sample input:

0 0 4 0 0 4 5
1 1
3 3
4 4
5 5
-1 0

Sample output:

Edge hints: the point (4, 4) in the sample lies exactly on the circle, and the strict test must not count it. The determinant reaches about 10^26 at these limits, so use 128-bit integers in C++.

Show the answer

Use the in-circle determinant. Subtract the test point d from a, b and c, then take the determinant of the three rows (x, y, x^2 + y^2). When a, b and c are counterclockwise, a positive value means d is strictly inside. I checked the key against a circumcentre computed with exact fractions, on random inputs.

def p12(data):
    a = (data[0], data[1]); b = (data[2], data[3]); c = (data[4], data[5])
    n = data[6]
    cnt = 0
    for i in range(n):
        d = (data[7 + 2 * i], data[8 + 2 * i])
        adx, ady = a[0] - d[0], a[1] - d[1]
        bdx, bdy = b[0] - d[0], b[1] - d[1]
        cdx, cdy = c[0] - d[0], c[1] - d[1]
        det = (adx * adx + ady * ady) * (bdx * cdy - cdx * bdy) \
            - (bdx * bdx + bdy * bdy) * (adx * cdy - cdx * ady) \
            + (cdx * cdx + cdy * cdy) * (adx * bdy - bdx * ady)
        cnt += det > 0
    return [str(cnt)]

Common mistakes

Floating point for a turn or a sign. The symptom is the first example in this lesson: exact -1, float 0.0. Use integer cross products for every decision and convert to float only for the final printed value.

Keeping collinear points when the statement says to drop them, or the reverse. The sample hull shows the change: 4 corners in one version and 5 vertices in the other. Read the statement for the words "corner" and "boundary", then build the hull to match.

Forgetting the degenerate inputs. Repeated points, all points on one line and a single point break many hull and distance routines. Test them before the random tests.

Overflow in C++. The limits in each problem show the largest values, and some of them exceed 64 bits. Estimate the largest product before you write the code, then pick the integer size.

Square roots where a comparison is enough. Problems 2, 8 and 9 can be decided with squared values, which keeps the answer exact.

Checklist

Name the predicate for each problem before writing code.
Check the sample, then a brute force on random small inputs that include repeated points and collinear points.
Estimate the largest intermediate value and choose the integer size from that estimate.
Use no floating point for any yes-or-no decision.
Re-read the statement for "corner", "boundary", "inside" and "on the circle", since each one changes the answer.

Note to write

After you solve the set, write one line per problem in this form, and keep it with your code.

Problem 9: predicate cross^2 against R2 * len2; edge case: line tangent, R2 equal.

A good note names the predicate and one edge case that changed the answer. A weak note says only "used cross product".

Summary

The twelve problems use the module's predicates: orientation, dot sign, exact squared distance, the Manhattan rotation, reflection and the in-circle determinant. Each answer key was checked against an independent brute force on random small inputs, and the samples above are the outputs of those keys. Name the predicate first, estimate the largest value, and test the degenerate inputs.