Unit 24: Shapes and Sweeps

The cross product, and what its sign means

For two steps (x1, y1) and (x2, y2), the cross product is x1 * y2 - x2 * y1.

Positive means the second step turns left from the first, negative means right, and zero means they are in line. That sign is most of contest geometry.

Python

def cross(ax, ay, bx, by):
    return ax * by - bx * ay

print(cross(1, 0, 0, 1))
print(cross(1, 0, 0, -1))
print(cross(1, 0, 2, 0))

It prints

1
-1
0

Which side of a line is a point on?

Take the step from a to b, and the step from a to the point. The cross product of those two says which side the point is on — and zero says it is exactly on the line.

With whole-number coordinates this is exact. No angles, no square roots, nothing to round.

Python

def side(ax, ay, bx, by, px, py):
    value = (bx - ax) * (py - ay) - (px - ax) * (by - ay)
    if value > 0:
        return "left"
    if value < 0:
        return "right"
    return "on the line"

print(side(0, 0, 4, 0, 2, 3))
print(side(0, 0, 4, 0, 2, -3))
print(side(0, 0, 4, 0, 2, 0))

It prints

left
right
on the line

And it gives you area for free

The cross product of the two sides of a triangle is twice its area, with a sign for which way round the corners go.

Keeping the doubled value avoids ever dividing by 2, so the arithmetic stays in whole numbers — which is exactly what you want a judge comparing your answer to.

Python

def twice_area(ax, ay, bx, by, cx, cy):
    return abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay))

print(twice_area(0, 0, 4, 0, 0, 3))
print(twice_area(0, 0, 4, 0, 2, 3))
print(twice_area(0, 0, 4, 0, 8, 0))

It prints

12
12
0

Distances: compare the squares

The distance between two points needs a square root, which is a decimal, which rounds. If all you are doing is comparing — which point is nearer, is this within r — compare the squared distances instead and stay exact.

Only take a square root when the answer itself has to be printed as a length.

Python

def squared(ax, ay, bx, by):
    return (ax - bx) ** 2 + (ay - by) ** 2

print(squared(0, 0, 3, 4))
print(squared(0, 0, 5, 0))
print(squared(0, 0, 3, 4) == squared(0, 0, 5, 0))

It prints

25
25
True

Four turns decide it

Two segments cross when each one has the other's ends on opposite sides of it.

So four cross products: the two ends of the second segment against the first, and the two ends of the first against the second. If both pairs have opposite signs, they cross.

Python

def turn(ax, ay, bx, by, px, py):
    value = (bx - ax) * (py - ay) - (px - ax) * (by - ay)
    if value > 0:
        return 1
    if value < 0:
        return -1
    return 0

def crosses(a, b, c, d):
    t1 = turn(a[0], a[1], b[0], b[1], c[0], c[1])
    t2 = turn(a[0], a[1], b[0], b[1], d[0], d[1])
    t3 = turn(c[0], c[1], d[0], d[1], a[0], a[1])
    t4 = turn(c[0], c[1], d[0], d[1], b[0], b[1])
    return t1 * t2 < 0 and t3 * t4 < 0

print(crosses((0, 0), (4, 4), (0, 4), (4, 0)))
print(crosses((0, 0), (1, 1), (2, 2), (3, 3)))
print(crosses((0, 0), (4, 0), (2, 1), (2, 5)))

It prints

True
False
False

The awkward cases are the zeroes

A cross product of 0 means an end sits exactly on the other segment — touching rather than crossing. The strict test above says False for that, which is right for some problems and wrong for others.

Read the statement. "Touching counts as intersecting" is a sentence that decides your code, and it is easy to skim past.

Python

def turn(ax, ay, bx, by, px, py):
    value = (bx - ax) * (py - ay) - (px - ax) * (by - ay)
    if value > 0:
        return 1
    if value < 0:
        return -1
    return 0

print(turn(0, 0, 4, 0, 2, 0))
print(turn(0, 0, 4, 0, 4, 0))
print(turn(0, 0, 4, 0, 2, 1))

It prints

0
0
1

Counting crossings without checking every pair

A thousand segments make half a million pairs — fine. A hundred thousand make five thousand million, which is not.

That is what lesson 4 is for: sort the ends and sweep, so only segments that overlap in the sweep direction are ever compared.

Stretch a band round the points and let go

The shape it snaps to is the convex hull — the smallest shape containing every point, with no dents.

It answers "which points are on the outside", "what is the widest pair", and half the questions about a cloud of points.

Sort by x, then walk along keeping only left turns

Take the points in order of x. Push each onto a list, and while the last three make a right turn, throw the middle one away — it was a dent.

That builds the bottom of the hull. Do it again from the other end for the top, and join them.

Python

points = [(0, 0), (1, 1), (2, 0), (2, 3), (4, 3), (4, 0)]

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def half(order):
    chain = []
    for p in order:
        while len(chain) >= 2 and cross(chain[-2], chain[-1], p) <= 0:
            chain.pop()
        chain.append(p)
    return chain

ordered = sorted(points)
lower = half(ordered)
upper = half(ordered[::-1])
print(lower)
print(upper)
print(lower[:-1] + upper[:-1])

It prints

[(0, 0), (4, 0), (4, 3)]
[(4, 3), (2, 3), (0, 0)]
[(0, 0), (4, 0), (4, 3), (2, 3)]

Four corners, two thrown away

The points (1, 1) and (2, 0) are inside the shape, so the band never touches them. The hull is (0, 0), (4, 0), (4, 3), (2, 3).

The cost is the sorting — n log n — because each point is pushed once and popped at most once.

The comparison decides what happens to flat points

<= 0 throws away a point that is exactly on an edge; < 0 keeps it. Some problems want the corners only, some want every point on the boundary.

That single character is the whole difference, and it is a classic wrong answer.

A line moving across the picture

Imagine a vertical line sliding left to right. Nothing happens except at the moments something starts or ends.

So sort those moments, walk through them in order, and keep a count. Everything between two events is unchanged, so there is nothing to look at there.

How many things overlap at once?

Five bookings for a room. Turn each into two events — a +1 where it starts and a -1 where it ends — sort them, and run a total.

The biggest the total ever gets is the answer: three rooms needed. No pair of bookings was ever compared.

Python

bookings = [(1, 4), (2, 6), (5, 8), (7, 9), (3, 5)]

events = []
for start, end in bookings:
    events.append((start, 1))
    events.append((end, -1))
events.sort()

now = 0
best = 0
for position, change in events:
    now += change
    best = max(best, now)
    print(position, change, now)

print("most at once", best)

It prints

1 1 1
2 1 2
3 1 3
4 -1 2
5 -1 1
5 1 2
6 -1 1
7 1 2
8 -1 1
9 -1 0
most at once 3

The tie at position 5 is not an accident

One booking ends at 5 and another starts at 5. Sorting puts -1 before +1, because -1 is smaller — so the room is freed before it is taken, and the count stays at 2.

If a problem says a booking ending at 5 still clashes with one starting at 5, you must sort the other way round. One character, two different answers.

Counting overlapping pairs, still without pairs

Walk the same events. When something starts, it overlaps everything currently open — so add the current count.

Five bookings, five overlapping pairs, and the loop never looked at a pair.

Python

bookings = [(1, 4), (2, 6), (5, 8), (7, 9), (3, 5)]

events = []
for start, end in bookings:
    events.append((start, 1))
    events.append((end, -1))
events.sort()

now = 0
pairs = 0
for position, change in events:
    if change == 1:
        pairs += now
        now += 1
    else:
        now -= 1

slow = 0
for i in range(len(bookings)):
    for j in range(i + 1, len(bookings)):
        if bookings[i][0] < bookings[j][1] and bookings[j][0] < bookings[i][1]:
            slow += 1

print(pairs, slow)

It prints

5 5

What the sweep really bought

The slow loop is n * n. The sweep is the cost of sorting, n log n, and answers the same question exactly.

That is the same bargain as unit 4's two pointers and unit 5's binary search: put the data in order, then walk it once. Most of this track is that sentence.