Why this matters when you build with AI
Ask an AI tool for the closest pair of points and you will often get one of two programs. The first checks every pair, which is O(n squared) and too slow when n is 200,000. The second is a divide and conquer with a strip step that looks right and is wrong in a corner. Both pass the sample, because samples are small and rarely have ties.
Segment intersection is worse. A generated version often checks only proper crossings, where two segments cross in the middle. It then says "no" when two segments share an endpoint, or when they lie on one line and overlap. Judges test exactly those cases, because they are where code breaks.
The cheap way to catch these bugs is a brute force. Write the slow version that checks every pair, generate thousands of small random inputs with coordinates from 0 to 3 (so that ties and touching happen constantly), and compare the two outputs. If the fast version disagrees on one input, print that input and trace it by hand. The random tests in this lesson do exactly that, and the results are reported below.
AI tools also tend to replace exact integer tests with floating point and an eps constant chosen without thought. For these two problems the exact integer version is short, so there is no reason to accept the float version. You need to know the rules well enough to read the generated code and spot the missing case.
The idea: a line that moves across the plane
A sweep line is an imaginary vertical line that starts at the far left and moves to the right. It stops only at certain x coordinates, called events. A point's x coordinate is an event, and so is the left or right end of a segment. Between events nothing changes, so the algorithm only needs to look at what happens at each stop.
The line keeps a status: the set of objects it currently crosses, sorted by height along the line. The status is stored in an ordered set. An ordered set keeps its items in sorted order and supports insert, erase and lower_bound (find the first item not less than a value) in O(log n) time each. The C++ std::set is one, and so is std::map with a key. Python has no built-in one, so the sweep is usually written in C++ or Java.
Here is the smallest example. Take three points (1, 5), (3, 2) and (4, 4). Sorted by x they come in the order (1, 5), then (3, 2), then (4, 4). A sweep that visits them in that order sees each point once. When the line reaches (4, 4), the status holds the points with x at most 4. Sorted by y they are (3, 2), then (4, 4), then (1, 5). The sweep does not need to remember anything else.
The sweep works only when the status order stays fixed while items sit in it. If two items swap order while both are in the set, the set becomes corrupt and lookups return wrong answers. Most of the care in this lesson goes into keeping that order consistent.
Closest pair with a sweep
The problem: given n points with integer coordinates, find the smallest squared distance between two of them and print one pair that achieves it. Squared distance is dx * dx + dy * dy. It avoids a square root and stays an integer, so it can be compared exactly.
The window that keeps the work small
Let best be the smallest squared distance found so far. Let d be its square root, so d is the distance a new point must beat. Sort the points by x and sweep them in that order. When the sweep is at point p, a point q to its left can beat best only if p.x - q.x is less than d. So the set only needs to hold the points within d to the left of the sweep. Points further left are removed from the set for good, because best never grows, so they can never matter again.
Inside the set the points are ordered by y. A point q in the window can beat best only if its y is within d of p.y. So a query is a range search on y, from p.y - d to p.y + d. The search starts at lower_bound and walks forward while the y value is still in range.
Why does this stay fast? The points that remain in the query box have x in [p.x - d, p.x] and y in [p.y - d, p.y + d]. Any two of them are at least d apart, because d is the best distance so far. A box of this size can hold only a fixed small number of points that are pairwise that far apart. So each query examines a constant number of set members, and each point is inserted once and removed once. The total is O(n log n), the time of the sort plus the set operations. This is the textbook argument, and the random tests below check the code, not the constant.
A worked example by hand
Use six points: (0, 0), (10, 0), (4, 1), (4, 9), (9, 8), (3, 0). Sorted by x, then y, they are (0, 0), (3, 0), (4, 1), (4, 9), (9, 8), (10, 0). Start with best set to the squared distance of the first two points, which is (3 - 0)^2 + 0 = 9.
- Point
(0, 0). The set is empty, so there is nothing to query. Insert it. - Point
(3, 0). Remove nothing, since(3 - 0)^2 = 9is not greater thanbest = 9. The reference usesD = 4, one more than the whole part of the square root of 9, so the y range is[-4, 4]. It contains(0, 0), whose squared distance is 9, which does not beat 9. Insert(3, 0). - Point
(4, 1). Remove(0, 0), because(4 - 0)^2 = 16is greater than 9. Keep(3, 0), because(4 - 3)^2 = 1. Query the y range[-3, 5], which contains(3, 0). The squared distance is1 + 1 = 2, which beats 9. Setbestto 2 and remember the pair(3, 0),(4, 1). Insert(4, 1). - Point
(4, 9). Keep both points in the set, since their squared x distances are 0 and 1, and neither is greater thanbest = 2. Withbest = 2the window isD = 2, so the query range is[7, 11], and nothing in the set has y in that range. Insert(4, 9). - Point
(9, 8). Remove(3, 0),(4, 1)and(4, 9), since their x distances from 9 are 6, 5 and 5, all greater than 2. Query the range around y = 8. The set is empty. Insert(9, 8). - Point
(10, 0). Keep(9, 8), since(10 - 9)^2 = 1is not greater than 2. The query range[-2, 2]does not contain y = 8. Nothing beats 2.
The answer is best = 2, from the pair (3, 0) and (4, 1). The reference program prints exactly this, as shown below. Note that step 3 found the answer while step 4 found nothing, which is typical: most points cost one range query that returns nothing.
The reference program
The program below holds both methods, the sweep and divide and conquer. It is C++17 and compiles with g++ -O2 -std=c++17 -Wall -Wextra without warnings. Run it with no argument for the sweep, or with the argument dc for the divide and conquer.
// closest.cpp: closest pair of integer points, by a sweep line with an ordered set, or by divide and conquer.
// Input: N, then N lines "x y" with |x|, |y| <= 1e9 and N >= 2.
// Output: the squared distance of a closest pair, then the coordinates of the two points.
// Argument "dc" uses divide and conquer instead of the sweep.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P { ll x, y; };
// Squared distance. With |x|, |y| <= 1e9 each difference is at most 2e9, so the sum is at most 8e18.
ll d2(const P& a, const P& b) {
ll dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
// Sweep line. Points are sorted by x. The sweep keeps in a set the points that are within sqrt(best)
// to the left of the current point, ordered by y. A new point is compared only with set members whose
// y is within sqrt(best) of its own y.
ll closestSweep(vector<P> p, P& ra, P& rb) {
int n = p.size();
sort(p.begin(), p.end(), [](const P& a, const P& b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
ll best = d2(p[0], p[1]);
ra = p[0];
rb = p[1];
set<pair<ll, ll>> active; // (y, x) of the points still in the window
int left = 0; // first point (in x order) still in the window
for (int i = 0; i < n; i++) {
// Points too far to the left can never be closer than best to p[i] or to any later point.
while (left < i && (p[i].x - p[left].x) * (p[i].x - p[left].x) > best) {
active.erase({p[left].y, p[left].x});
left++;
}
// D is an integer at least sqrt(best), so every point within sqrt(best) in y is in the range.
ll D = (ll)sqrtl((long double)best) + 1;
for (auto it = active.lower_bound({p[i].y - D, LLONG_MIN});
it != active.end() && it->first <= p[i].y + D; ++it) {
P q{it->second, it->first};
ll dd = d2(p[i], q);
if (dd < best) {
best = dd;
ra = q;
rb = p[i];
}
}
if (best == 0) return 0; // two equal points: nothing can be closer
active.insert({p[i].y, p[i].x});
}
return best;
}
// Divide and conquer. On return p[l, r) is sorted by y. Returns the best squared distance in [l, r).
ll rec(vector<P>& p, int l, int r, P& ra, P& rb) {
if (r - l <= 3) {
ll best = LLONG_MAX;
for (int i = l; i < r; i++)
for (int j = i + 1; j < r; j++) {
ll dd = d2(p[i], p[j]);
if (dd < best) {
best = dd;
ra = p[i];
rb = p[j];
}
}
sort(p.begin() + l, p.begin() + r, [](const P& a, const P& b) { return a.y < b.y; });
return best;
}
int m = (l + r) / 2;
ll midx = p[m].x;
P a1, b1, a2, b2;
ll dl = rec(p, l, m, a1, b1);
ll dr = rec(p, m, r, a2, b2);
ll best = dl;
ra = a1;
rb = b1;
if (dr < best) {
best = dr;
ra = a2;
rb = b2;
}
inplace_merge(p.begin() + l, p.begin() + m, p.begin() + r,
[](const P& a, const P& b) { return a.y < b.y; });
// Strip: points within sqrt(best) of the dividing line, already in y order.
vector<P> strip;
for (int i = l; i < r; i++) {
ll dx = p[i].x - midx;
if (dx * dx < best) strip.push_back(p[i]);
}
// In y order, a point can only be closer than best to the next few points, so stop early.
for (size_t i = 0; i < strip.size(); i++)
for (size_t j = i + 1; j < strip.size(); j++) {
ll dy = strip[j].y - strip[i].y;
if (dy * dy >= best) break;
ll dd = d2(strip[i], strip[j]);
if (dd < best) {
best = dd;
ra = strip[i];
rb = strip[j];
}
}
return best;
}
ll closestDC(vector<P> p, P& ra, P& rb) {
sort(p.begin(), p.end(), [](const P& a, const P& b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
return rec(p, 0, (int)p.size(), ra, rb);
}
int main(int argc, char** argv) {
bool useDC = argc > 1 && string(argv[1]) == "dc";
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> p(n);
for (auto& q : p) cin >> q.x >> q.y;
P a, b;
ll best = useDC ? closestDC(p, a, b) : closestSweep(p, a, b);
cout << best << "\n" << a.x << " " << a.y << " " << b.x << " " << b.y << "\n";
return 0;
}Save the program as closest.cpp and run it on the six points. The output is:
2
3 0 4 1The divide and conquer gives the same output on this input. Its method is in the code above: sort by x, split at the middle, solve each half, then check a strip of points near the split line. Shamos and Hoey published a divide and conquer closest-pair algorithm in 1975 at the 16th Annual Symposium on Foundations of Computer Science, pages 151 to 162 (DOI 10.1109/SFCS.1975.8). That is the source of the O(n log n) divide and conquer, not of the sweep above. The sweep with an ordered set is a standard textbook method, and I did not verify a single original paper for it, so this lesson does not name one.
Checking both methods
I checked the program against a brute force that compares every pair. The test ran 160,040 random inputs: 40,000 each with coordinates from -2 to 2, -5 to 5, -20 to 20, and -1,000,000,000 to 1,000,000,000, with 2 to 41 points each, plus 40 larger inputs of 2,000 to 4,999 points that were compared between the two fast methods. Both methods matched the brute force on every small input, and they matched each other on every large one. The brute force was not run on the large inputs because it is too slow there.
Both methods agree on the distance, but they may print the two points in a different order. On a random 1,000-point input the sweep printed -12574165 578850595 -11737030 577406091 and the divide and conquer printed the same two points reversed. A judge that asks for a distance only does not care. A judge that asks for a pair must accept either order, so check the problem statement.
Timing on a random input of 200,000 points, on the WSL2 machine used for this lesson, was about 0.05 seconds for the sweep and 0.07 seconds for the divide and conquer. Your numbers will differ with the machine and the compiler flags. The point of the timing is that both are fast, not which is faster.
Segment events: does any pair of segments touch?
The problem: given N segments, each with two integer endpoints, print YES if any two of them share at least one point, and NO otherwise. Sharing a point includes touching at an endpoint, crossing in the middle, and overlapping on one line.
The event rules
Each segment has a left end and a right end. Put the left end first, comparing x and then y, so every segment runs from left to right. A vertical segment has the same x at both ends, so it is a special case that the rules below handle.
Each segment produces two events. An insert event sits at its left x. A remove event sits at its right x. Sort all events by x. Where two events share an x, insert events go before remove events. The reason: two segments that touch at some x must both be in the status at that moment, so neither may leave before the other arrives. The seg_ex2 example below depends on this rule.
The status is ordered by height. The height of a segment at an x is its y at that x. Two segments in the status are compared at the later of their two left ends, since both exist there. For a vertical segment there is no single height, so the program uses its lower end.
On insert, check the new segment against the neighbour just above it and the neighbour just below it in the status. On remove, check the two segments that become neighbours after the removal. If any check touches, answer YES and stop. If the sweep finishes with no touch, answer NO.
A brief reason this finds every touch: if two segments touch, there is a leftmost touching point. Just before the sweep reaches it, the two segments are next to each other in the status, so the check made when they became neighbours catches them. This is the standard sweep argument for segment detection, which the chapter on line segment intersection of de Berg, Cheong, van Kreveld and Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, 2008, covers in its sweep-line form. I did not re-derive that argument for the rules here, so treat the claim as the textbook's, and rely on the tests below for this program.
I checked the program against a brute force that compares every pair. The test ran 300,000 random sets of 2 to 8 segments, 60,000 sets for each of five coordinate ranges (-2 to 2, -4 to 4, -8 to 8, -30 to 30, and -1,000,000,000 to 1,000,000,000). One segment in four was vertical, to exercise that rule. About 74 percent of the sets had a touching pair, so the NO answers are the smaller share, and the program and the brute force agreed on every set.
Exact comparisons
A height is usually a fraction. The height of a segment with endpoints (0, 0) and (3, 2) at x = 1 is 2/3. Comparing two fractions with doubles can be off in the last bit, which is exactly where ties happen. The program compares fractions by cross multiplication with __int128, so each comparison is exact. With coordinates up to 1e9 the products reach about 1e28, which fits in 128 bits and does not fit in 64.
The reference program
The program is C++17 and compiles with g++ -O2 -std=c++17 -Wall -Wextra with no warnings. It reads N, then N lines ax ay bx by, and prints YES or NO.
// segments.cpp: does any pair of closed segments share at least one point? Sweep line with exact arithmetic.
// Input: N, then N lines "ax ay bx by" with |coordinate| <= 1e9. Output: YES or NO.
// Each segment is first put in left-to-right order. Events are sorted by x, with insertions before removals.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
struct P { ll x, y; };
struct S { P a, b; }; // a is the left end (smaller x, then smaller y)
ll orient(P a, P b, P c) { // positive when c is left of the directed line a -> b
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool inBox(P p, P a, P b) {
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
// Do the closed segments ab and cd share a point? Exact. Also works when a == b or c == d.
bool touch(P a, P b, P c, P d) {
ll d1 = orient(c, d, a), d2 = orient(c, d, b), d3 = orient(a, b, c), d4 = orient(a, b, d);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return true;
if (d1 == 0 && inBox(a, c, d)) return true;
if (d2 == 0 && inBox(b, c, d)) return true;
if (d3 == 0 && inBox(c, a, b)) return true;
if (d4 == 0 && inBox(d, a, b)) return true;
return false;
}
vector<S> segs;
// The height of segment s at x, as the fraction num / den with den > 0.
// A vertical segment has no single height; it uses its lower end.
struct Frac { i128 num, den; };
Frac heightAt(const S& s, ll x) {
if (s.a.x == s.b.x) return {s.a.y, 1};
i128 den = s.b.x - s.a.x;
i128 num = (i128)s.a.y * den + (i128)(s.b.y - s.a.y) * (x - s.a.x);
return {num, den};
}
// Order two segments by height at the later of their two left ends. Both exist at that x, and
// that x is the sweep position when one of them is inserted.
struct Cmp {
bool operator()(int i, int j) const {
const S& s = segs[i];
const S& t = segs[j];
ll x = max(s.a.x, t.a.x);
Frac fi = heightAt(s, x), fj = heightAt(t, x);
return fi.num * fj.den < fj.num * fi.den;
}
};
struct Ev { ll x; int type; int id; }; // type 0 = insert, 1 = remove
bool anyTouch(const vector<S>& all) {
segs = all;
int n = segs.size();
vector<Ev> ev;
for (int i = 0; i < n; i++) {
ev.push_back({segs[i].a.x, 0, i});
ev.push_back({segs[i].b.x, 1, i});
}
sort(ev.begin(), ev.end(), [](const Ev& p, const Ev& q) { return p.x != q.x ? p.x < q.x : p.type < q.type; });
set<int, Cmp> st;
vector<set<int, Cmp>::iterator> where(n);
for (const Ev& e : ev) {
if (e.type == 0) {
auto nxt = st.lower_bound(e.id); // first segment not below the new one
if (nxt != st.end() && touch(segs[*nxt].a, segs[*nxt].b, segs[e.id].a, segs[e.id].b)) return true;
if (nxt != st.begin()) {
auto prv = prev(nxt);
if (touch(segs[*prv].a, segs[*prv].b, segs[e.id].a, segs[e.id].b)) return true;
}
where[e.id] = st.insert(nxt, e.id);
} else {
auto it = where[e.id];
if (it != st.begin() && next(it) != st.end()) {
auto prv = prev(it);
auto nxt = next(it);
if (touch(segs[*prv].a, segs[*prv].b, segs[*nxt].a, segs[*nxt].b)) return true;
}
st.erase(it);
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<S> in(n);
for (auto& s : in) {
cin >> s.a.x >> s.a.y >> s.b.x >> s.b.y;
if (s.a.x > s.b.x || (s.a.x == s.b.x && s.a.y > s.b.y)) swap(s.a, s.b);
}
cout << (anyTouch(in) ? "YES" : "NO") << "\n";
return 0;
}Five small inputs show the rules at work. Each input file starts with N and then one segment per line. The segments are seg_ex1 with (0,0)-(4,4), (0,4)-(4,0) and (6,0)-(6,5); seg_ex2 with (0,0)-(2,0), (2,0)-(4,1) and (5,5)-(6,6); seg_ex3 with the first two segments of seg_ex2; seg_ex4 with (0,0)-(1,0) and (2,0)-(4,1); and seg_ex5 with (0,0)-(0,5) and (0,3)-(4,3). The real output of the program is:
seg_ex1: YES
seg_ex2: YES
seg_ex3: YES
seg_ex4: NO
seg_ex5: YESIn seg_ex1 the first two segments cross at (2, 2). In seg_ex2 they share the point (2, 0). In seg_ex4 the segments lie on one line but a gap from x = 1 to x = 2 separates them, so the answer is NO. In seg_ex5 the vertical segment passes through (0, 3), which is the end of the horizontal one.
What breaks when the event order is wrong
To see why the insert-first rule matters, change one comparison in the program so that removals come before inserts at the same x. The change is to replace p.type < q.type with p.type > q.type in the sort. Run the changed program on the same files:
seg_ex2.txt: NO
seg_ex3.txt: NO
seg_ex5.txt: (no output, the process exited with code 139, a segmentation fault)The two segments in seg_ex2 touch at (2, 0), which is the right end of one and the left end of the other. With removals first, the first segment leaves the status before the second arrives, so the check never happens. The answer NO is wrong.
The crash in seg_ex5 has a plain cause. The vertical segment starts and ends at x = 0, and with removals first its remove event runs before its insert event. The program then reads where[e.id] before it was set, and the erase call crashes. Code generated by an AI tool often has this exact order, because the sort looks symmetric. The output shows that it is not.
Hands-on exercise
Work on your own machine. Save the closest pair program as closest.cpp, and compile it with g++ -O2 -std=c++17 -Wall -Wextra -o closest closest.cpp. Run it on the six-point example from this lesson. You should see 2 and then 3 0 4 1.
Then write a random tester. Save this as check_closest.py in the same folder, and run it with python3 check_closest.py. It compares both methods with a brute force on 2,000 random inputs. Your output should be mismatches: 0.
import random
import subprocess
random.seed(1)
def brute(p):
return min((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 for i, a in enumerate(p) for b in p[i + 1:])
bad = 0
for trial in range(2000):
n = random.randint(2, 30)
R = random.choice([3, 10, 10**9])
pts = [(random.randint(-R, R), random.randint(-R, R)) for _ in range(n)]
text = f"{n}\n" + "".join(f"{x} {y}\n" for x, y in pts)
for mode in ([], ["dc"]):
out = subprocess.run(["./closest", *mode], input=text, capture_output=True, text=True, check=True).stdout.split()
if int(out[0]) != brute(pts):
bad += 1
print("mismatches:", bad)Last, time both methods on a large input. Generate 200,000 points with a seed, and time each run with time:
import random
import sys
random.seed(int(sys.argv[1]))
n = int(sys.argv[2])
print(n)
for _ in range(n):
print(random.randint(-10**9, 10**9), random.randint(-10**9, 10**9))Run it as python3 gen.py 1 200000 > big.txt, then time ./closest < big.txt and time ./closest dc < big.txt. Your timings will differ from the ones above. Both should print the same first number.
Then write a segment tester in the same way: generate random segments with coordinates from -2 to 2, count how often your program and a brute force that checks every pair disagree, and make sure both YES and NO cases occur in your run.
Common mistakes
Removals before inserts at the same x. This is the bug shown above. A touching pair at an endpoint is reported as NO, and a vertical segment can crash the program with a segmentation fault, exit code 139 on the test machine. The fix is one comparison in the sort. Check it with the seg_ex2 and seg_ex5 files.
Comparing squared distances or heights as doubles. A squared distance can be as large as 8e18 when coordinates reach 1e9. A double holds 53 exact bits, about 9.0e15, so two different large integers can become equal once stored as doubles. Use long long for distances and __int128 for fractions. The closest pair program never uses doubles except for the square root that sizes the search window, and that value is only used to make the window slightly too big, which is safe.
Using std::set keyed on y alone. Two points can share a y value. If the key is only y, the second point is treated as equal to the first and silently dropped, so the closest pair can be missed. The reference program uses the pair (y, x) as the key, which keeps points with equal y distinct. I did not run this broken variant, so the failure above is the logical consequence, not an observed output.
Forgetting that the window must shrink. The window is defined by the current best, and best only goes down. A program that uses a window fixed at the start stays correct but can scan far more points than needed. The reference recomputes the removal condition for every point.
Assuming the sweep reports the same pair as the brute force. The distance is unique, but the pair may not be. A judge that accepts any closest pair needs the distance only, and a judge that wants a specific pair needs the statement's tie-breaking rule. Read it before writing the output.
Using the segment program with unsorted endpoints. The reference swaps endpoints so that a is the left end. A program that skips this step gives wrong orders for segments given right to left, and the comparator uses a.x as the left end. Check the normalization step first when a case fails.
Checklist
- Sort events by x, and put insert events before remove events at the same x.
- Normalize each segment so its left end comes first, and use the lower end for a vertical segment.
- Compare heights as exact fractions, with cross multiplication in
__int128. - Keep the closest pair window tied to the current
best, and remove points that fall out of it. - Use
(y, x)as the key for points, so equal y values do not collide. - Check every change against a brute force on random inputs with small coordinates, where ties are common.
- Run the degenerate inputs by hand: duplicate points, a vertical segment, a point segment, and two segments that share one endpoint.
Summary
A sweep line turns a two-dimensional question into a sequence of events in x order, with an ordered set holding the active items. For closest pair, the set holds points within the best distance of the sweep, and a y range query checks only the few that can win, which gives O(n log n). For segment touching, the set holds segments in height order, and each insert or remove checks only its neighbours. Keep the event order and the exact comparisons correct, and the sweep is short and reliable.
Practice
Practice 1: closest pair on a line
Given the points (-7, 0), (3, 0), (4, 0), (12, 0) and (20, 0), find the squared distance of the closest pair by hand.
Hint: all points lie on the x axis, so the squared distance is the square of the x gap.
Show the answer
The closest pair is (3, 0) and (4, 0), with squared distance 1. On a line, the closest partner of any point is one of its two neighbours in sorted order, so the sweep only needs to compare each point with the points next to it.
Practice 2: four points, exact
Find the closest pair among (0, 0), (5, 1), (2, 2) and (6, 6), and give its squared distance.
Hint: list the six squared distances in a small table before looking for the smallest.
Show the answer
The pair (0, 0) and (2, 2) has squared distance 8, which is the smallest. The other five squared distances are 10 for (5, 1) and (2, 2), 26 for (0, 0) and (5, 1), 26 for (5, 1) and (6, 6), 32 for (2, 2) and (6, 6), and 72 for (0, 0) and (6, 6). The reference program prints 8 and then 0 0 2 2 on this input, which matches the table.
Practice 3: why insert first
Two segments are (0, 0) to (2, 0) and (2, 0) to (5, 3). Explain in two or three sentences what the sweep does at x = 2 if inserts come before removes, and what happens if removes come first.
Hint: think about which segment is in the status when the other one is inserted.
Show the answer
With inserts first, the segment from (2, 0) is inserted while the first segment is still in the status, so the check against its neighbour finds the shared point (2, 0) and the answer is YES. With removes first, the first segment leaves the status before the second is inserted, so no check happens and the answer is wrong.
Practice 4: report the pair
Change the segment program so that, when it finds a touching pair, it prints the two segment indices as well as YES. Indices are the position of the segment in the input, starting from 0. Describe the one place where the change is made.
Hint: the touching check is made in several places, but the indices are known at each of them.
Show the answer
Replace each return true; after a touch call with a print of the two indices and a return. The indices are the segment ids: *nxt and e.id at insert, *prv and e.id at the insert neighbour check, and *prv and *nxt at removal. The neighbour ids are stored in the set, so no extra data is needed. A simpler design is to change anyTouch to return a pair of ids and print them in main.