Circles and coordinate transforms

Why this matters when you build with AI

Ask an AI tool whether two circles intersect and you will usually get a function that computes the distance with sqrt, compares it with the sum of the radii, and adds 1e-9 for safety. That code passes small examples. With coordinates near one million it can call a pair of circles that barely miss "tangent", and with coordinates near one billion the same tolerance can be too large to tell a miss from a touch. Nothing in the output shows the error.

The same tools often rotate points with cos and sin and then compare the result with an integer. The rotated x coordinate of (1, 0) after two 45 degree turns is not zero, so an equality test fails and the program takes the wrong branch. These are the cases that judge data contains, because a test writer who wants a tangent case picks exact values.

The fix is to keep the inputs as integers and to compare squares. Integer geometry is exact as long as the numbers fit, and most problems with integer input fit in 64 bits or 128 bits. Floating point should appear only where the output needs decimals or where an angle is genuinely irrational. When you do use it, the tolerance should come from an argument about the numbers, not from habit.

Circles and lines with exact tests

A circle has a centre (x, y) and a radius r, with r at least 1 here. All points at distance exactly r from the centre lie on the circle. The tests in this section use integers only, so every answer is exact.

Two circles

Let the centres be A and B, with radii r1 and r2. Let d2 be the squared distance between the centres, (xA - xB)^2 + (yA - yB)^2. Compare squares rather than distances, because squares of integers are integers.

If d2 is zero and the radii are equal, the circles are identical. Their common points are infinite.
If d2 equals (r1 + r2)^2, the circles touch from outside at one point. This is tangent.
If d2 equals (r1 - r2)^2, one circle is inside the other and they touch at one point. This is tangent too, provided the radii differ, because (r1 - r2)^2 is zero only for equal radii.
If d2 is greater than (r1 + r2)^2, the circles are too far apart and share no point.
If d2 is less than (r1 - r2)^2, one circle is inside the other with no contact.
Otherwise the circles cross at exactly two points.

Worked example. Take the circles (0, 0, 2), (3, 0, 1) and (6, 0, 3). The first and second have d2 = 9 and (r1 + r2)^2 = 9, so they are tangent. The first and third have d2 = 36 and (r1 + r2)^2 = 25, so they are apart. The second and third have d2 = 9, (r1 - r2)^2 = 4 and (r1 + r2)^2 = 16. Since 9 lies strictly between 4 and 16, they cross at two points. The reference program below counts pairs in each class. The sample in the problem section below adds a fourth circle that is identical to the first.

A line and a circle

Write the line as a*x + b*y = c with integers a, b and c, where a and b are not both zero. Write the circle centre as (p, q) and its radius as r. The distance from the centre to the line is |a*p + b*q - c| / sqrt(a*a + b*b). Let v = a*p + b*q - c. The line meets the circle in two points when that distance is less than r, in one point when it equals r, and not at all when it is greater.

To stay exact, square both sides. The test becomes: compare v*v with r*r*(a*a + b*b). The left side is smaller, equal or larger, and the same holds for the distance. With inputs up to one million, v is at most about 2e12, its square about 4e24, which does not fit in 64 bits. __int128 holds it.

Worked example. For the line x + y = 0 (so a = 1, b = 1, c = 0) and the circle at (0, 0) with r = 1, v = 0, and the test is 0 < 2, so the line passes through two points. For x + y = 1 with the same circle, v = -1 and v*v = 1 while r*r*(a*a + b*b) = 2. The line is 0.707 from the centre and the circle has radius 1, so it crosses in two points. For x + y = 2, v*v = 4 and the right side is 2, so the line misses the circle.

Circumcircle

The circumcircle of three points is the unique circle through all three, when they are not on one line. Its centre is the point at equal distance from all three. Translate the first point to the origin, so the other two points become B and C with coordinates (bx, by) and (cx, cy). The centre relative to the origin is

ux = (cy * |B|^2 - by * |C|^2) / D and uy = (bx * |C|^2 - cx * |B|^2) / D,

where |B|^2 = bx*bx + by*by, |C|^2 = cx*cx + cy*cy and D = 2 * (bx*cy - by*cx). The centre is then the first point plus (ux, uy). When D is zero the three points are on a line, and there is no circumcircle.

Keep the centre as a fraction. The numerator and the denominator are integers, and the transforms program below prints them directly. Floating point is needed only to print a decimal value.

Worked example. Take (0, 0), (2, 0) and (0, 2). Then B = (2, 0), C = (0, 2), D = 2 * (2*2 - 0*0) = 8, |B|^2 = 4 and |C|^2 = 4. So ux = (2*4 - 0*4) / 8 = 1 and uy = (2*4 - 0*4) / 8 = 1. The centre is (1, 1) and the radius squared is 2, which matches the distance from (1, 1) to (0, 0).

Take (0, 0), (3, 4) and (1, 1). Here D = 2 * (3*1 - 4*1) = -2, so the program flips the signs of D and of the numerators. The centre comes out as (-8.5, 9.5), which is printed as -17/2 and 19/2, and the radius squared as 650/4, which is 162.5. You can check it: the distance from (-8.5, 9.5) to (0, 0) squared is 72.25 + 90.25 = 162.5.

Transforms of coordinates

A transform maps each point to a new point. Several standard ones keep integers exact, and one does not.

Translation adds a fixed vector to every point, (x, y) -> (x + dx, y + dy). It is exact for integers.

Reflection across an axis negates one coordinate, for example (x, y) -> (x, -y). It is exact.

Rotation by 90 degrees maps (x, y) to (-y, x). It is exact.

Rotation by 45 degrees is not exact in integers, because its matrix has 1/sqrt(2) in it. The map (x, y) -> (x + y, x - y) is a rotation by 45 degrees followed by a scaling by sqrt(2). It sends integers to integers, so it is exact, and distances change by the known factor. The next section uses it to turn a Manhattan distance into a box.

Scaling by an integer factor is exact. Scaling by a fraction produces fractions, which you can keep as numerator and denominator.

Inversion in the unit circle maps a point (x, y) that is not the origin to (x / N, y / N) with N = x*x + y*y. Points near the origin go far away and far points come close. Inversion maps circles and lines to circles and lines, which makes it useful for some problems. The coordinates are fractions with denominator N, so keep them as a numerator pair and a denominator.

The program below handles the exact tests and the transforms that stay exact. Run it with line, circum or invert as the argument.

The reference programs

All three programs are C++17, compile with g++ -O2 -std=c++17 -Wall -Wextra without warnings, and read integers from standard input. The first counts circle pairs for the problem in the next section.

// circles.cpp: count pairs of circles by how they meet. Centres and radii are integers, all tests are exact.
// Input: N, then N lines "x y r" with |x|, |y| <= 1e6 and 1 <= r <= 1e6, N <= 2000.
// Output, three lines: pairs that meet in exactly two points, pairs that touch in one point (tangent),
// and pairs of identical circles (infinitely many common points).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct C { ll x, y, r; };
 
// Squared distance of the centres is at most (2e6)^2 * 2 = 8e12, and (r1 + r2)^2 is at most 4e12:
// every value below fits in a signed 64-bit integer.
// Returns 0 (no common point), 1 (tangent), 2 (two points) or 3 (identical).
int classify(const C& a, const C& b) {
    ll dx = a.x - b.x, dy = a.y - b.y;
    ll d2 = dx * dx + dy * dy;                  // squared distance between centres
    if (d2 == 0 && a.r == b.r) return 3;
    ll s = a.r + b.r, t = a.r - b.r;
    if (d2 == s * s) return 1;                  // outside each other, touching at one point
    if (d2 == t * t) return 1;                  // one inside the other, touching at one point (t != 0 here)
    if (d2 > s * s) return 0;                   // too far apart
    if (d2 < t * t) return 0;                   // one inside the other, not touching
    return 2;                                   // |r1 - r2| < d < r1 + r2
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<C> c(n);
    for (auto& q : c) cin >> q.x >> q.y >> q.r;
    ll two = 0, tangent = 0, same = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int k = classify(c[i], c[j]);
            if (k == 2) two++;
            else if (k == 1) tangent++;
            else if (k == 3) same++;
        }
    cout << two << "\n" << tangent << "\n" << same << "\n";
    return 0;
}

The second program covers the circle-line test, the circumcircle and the exact transforms. It reads one case per line for the mode it is given.

// transforms.cpp: exact circle-line test, exact circumcentre and inversion.
// Usage: transforms line < in    with lines "a b c p q r": line a*x + b*y = c, circle centre (p, q), radius r (r >= 0)
//        transforms circum < in  with lines "ax ay bx by cx cy": three points
//        transforms invert < in  with lines "x y": point (x, y) inverted in the unit circle
// All inputs are integers with absolute value up to 1e6. Results are exact fractions printed as numerators and a denominator.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
 
// Circle-line position. The distance from the centre to the line is |a*p + b*q - c| / sqrt(a^2 + b^2).
// Compare squares to stay exact: (a*p + b*q - c)^2 against r^2 * (a^2 + b^2).
// Magnitudes: a*p + b*q - c is at most about 2e12 + 1e6, its square about 4e24, which fits in __int128.
const char* lineCircle(ll a, ll b, ll c, ll p, ll q, ll r) {
    i128 v = (i128)a * p + (i128)b * q - c;
    i128 lhs = v * v;
    i128 rhs = (i128)r * r * ((i128)a * a + (i128)b * b);
    if (lhs < rhs) return "TWO POINTS";
    if (lhs == rhs) return "TANGENT";
    return "NONE";
}
 
string i128str(i128 v) {
    if (v == 0) return "0";
    bool neg = v < 0;
    if (neg) v = -v;
    string s;
    while (v > 0) {
        s += char('0' + (int)(v % 10));
        v /= 10;
    }
    if (neg) s += '-';
    reverse(s.begin(), s.end());
    return s;
}
 
int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "line";
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (mode == "line") {
        ll a, b, c, p, q, r;
        while (cin >> a >> b >> c >> p >> q >> r) cout << lineCircle(a, b, c, p, q, r) << "\n";
    } else if (mode == "circum") {
        ll ax, ay, bx, by, cx, cy;
        while (cin >> ax >> ay >> bx >> by >> cx >> cy) {
            // Move A to the origin. Then the circumcentre (ux, uy) of the origin, b and c is
            // ux = (cy*|b|^2 - by*|c|^2) / D and uy = (bx*|c|^2 - cx*|b|^2) / D, with D = 2*(bx*cy - by*cx).
            ll Bx = bx - ax, By = by - ay, Cx = cx - ax, Cy = cy - ay;
            i128 D = 2 * ((i128)Bx * Cy - (i128)By * Cx);
            if (D == 0) {
                cout << "COLLINEAR, no circumcircle\n";
                continue;
            }
            i128 b2 = (i128)Bx * Bx + (i128)By * By, c2 = (i128)Cx * Cx + (i128)Cy * Cy;
            i128 nx = (i128)Cy * b2 - (i128)By * c2;
            i128 ny = (i128)Bx * c2 - (i128)Cx * b2;
            if (D < 0) {
                D = -D;
                nx = -nx;
                ny = -ny;
            }
            // Centre in the original frame: A + (nx / D, ny / D) = ((ax*D + nx) / D, (ay*D + ny) / D).
            i128 X = (i128)ax * D + nx, Y = (i128)ay * D + ny;
            // Squared radius: distance from the centre to A, as a fraction over D^2.
            i128 R2 = nx * nx + ny * ny;
            cout << "centre " << i128str(X) << " " << i128str(Y) << " over " << i128str(D)
                 << ", radius^2 " << i128str(R2) << " over " << i128str(D * D) << "\n";
        }
    } else if (mode == "invert") {
        ll x, y;
        while (cin >> x >> y) {
            // Inversion in the unit circle sends (x, y) to (x / N, y / N) with N = x^2 + y^2.
            i128 N = (i128)x * x + (i128)y * y;
            if (N == 0) {
                cout << "undefined at the origin\n";
                continue;
            }
            cout << "(" << i128str(x) << ", " << i128str(y) << ") -> (" << i128str(x) << " / " << i128str(N)
                 << ", " << i128str(y) << " / " << i128str(N) << ")\n";
        }
    }
    return 0;
}

The third program is the 45 degree reduction for the Manhattan problem in the next section.

// manhattan45.cpp: largest Manhattan distance between two points, found after a 45 degree rotation.
// Input: N, then N lines "x y" with |x|, |y| <= 1e9 and N >= 2.
// Output: the largest value of |dx| + |dy| over all pairs.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    // Rotate: u = x + y, v = x - y. For any two points, |dx| + |dy| = max(|du|, |dv|).
    // So the largest Manhattan distance is the larger of the two ranges, max(u) - min(u) and max(v) - min(v).
    ll uMin = LLONG_MAX, uMax = LLONG_MIN, vMin = LLONG_MAX, vMax = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        ll u = x + y, v = x - y;
        uMin = min(uMin, u);
        uMax = max(uMax, u);
        vMin = min(vMin, v);
        vMax = max(vMax, v);
    }
    cout << max(uMax - uMin, vMax - vMin) << "\n";
    return 0;
}

Run the programs on the small inputs in this lesson. The outputs below are real, from the machine used for this lesson.

circ_ex.txt (4 circles: (0,0,2), (3,0,1), (6,0,3), (0,0,2)) with circles:
1
2
1
 
circ_ex2.txt (3 circles: (0,0,2), (4,0,2), (10,0,1)) with circles:
0
1
0
 
line_ex.txt with transforms line:
TWO POINTS
TANGENT
NONE
TWO POINTS
 
circum_ex.txt with transforms circum:
centre 8 8 over 8, radius^2 128 over 64
centre -17 19 over 2, radius^2 650 over 4
COLLINEAR, no circumcircle
 
inv_ex.txt with transforms invert:
(3, 4) -> (3 / 25, 4 / 25)
(0, 2) -> (0 / 4, 2 / 4)
(1, 1) -> (1 / 2, 1 / 2)
 
man_ex.txt with manhattan45:
13

I checked each program against an independent version before writing this lesson. The circle counter matched a floating point check with a tolerance on 400 random sets of up to 12 circles with small coordinates. The circle-line test matched the same kind of float check on 2,985 random lines. The circumcentre and the radius squared matched exact Fraction arithmetic in Python on 1,500 random triangles, and the inversion matched the formula on 500 random points. The Manhattan program matched a brute force on 1,500 random sets, with coordinates up to one billion. The floating point checks are reliable only for small coordinates, which is why the near-tangent case above uses the exact program for its answer.

The first circle output matches the hand count in the section above. The line results are the four lines of line_ex.txt: the line x = 0 through the centre gives two points, the line x = 1 is tangent to the unit circle, x = 2 misses, and x + y = 0 passes through the centre. The circumcircle line centre 8 8 over 8 is the value (1, 1) from the worked example. The inversion output is what the formula gives, with the denominator N printed next to each coordinate.

The problem: count how circles meet

Statement, written for this lesson. You are given N circles, 2 <= N <= 2000. Each circle is given as three integers x y r, with |x| <= 10^6, |y| <= 10^6 and 1 <= r <= 10^6. Circles may repeat. Print three numbers, one per line: the number of pairs of circles that have exactly two common points, the number of pairs that have exactly one common point (tangent), and the number of pairs of identical circles.

Sample input:

Sample output:

1
2
1

Solution. Compare every pair. For each pair, use classify from circles.cpp. The test is exact, because it compares squared distances with squares of radius sums and differences. There are about two million pairs at N = 2000, so the double loop is fast enough. The sample has one pair of two-point circles (the second and third), two tangent pairs (the first and second, and the second and fourth) and one identical pair (the first and fourth).

Edge cases. Two identical circles have the same centre and radius, so d2 is zero and the radii are equal, and the program counts them as identical, not as a crossing pair. Concentric circles with different radii have d2 zero and fall through to the nested test, which gives no common point. Circles whose radii differ by exactly the distance between centres touch from inside, and the program counts them as tangent, because d2 equals (r1 - r2)^2 and the radii differ.

Why the integers fit. The largest squared distance is (2 * 10^6)^2 * 2 = 8 * 10^12, and the largest squared sum of radii is (2 * 10^6)^2 = 4 * 10^12. Both fit in a signed 64-bit integer. A 32-bit int would overflow as soon as a squared difference passes about 2.1 * 10^9, which is well below 4 * 10^12, so the code uses long long.

The problem: farthest Manhattan pair

Statement, written for this lesson. You are given N points, 2 <= N <= 200000, with integer coordinates |x|, |y| <= 10^9. The Manhattan distance between two points is |dx| + |dy|. Print the largest Manhattan distance over all pairs of points.

Sample input:

Sample output:

The naive solution checks all pairs and takes O(N squared) time, which is too slow for 200,000 points. The reduction makes it O(N). For any two real numbers a and b, |a| + |b| = max(|a + b|, |a - b|). Apply this to a = dx and b = dy. The Manhattan distance becomes max(|du|, |dv|), where u = x + y and v = x - y for each point. The largest value of max(|du|, |dv|) over all pairs is the larger of the two largest ranges: the range of u and the range of v. So the answer is max(maxU - minU, maxV - minV), computed in one pass.

Check on the sample. The four points give u = 0, 7, -1, 0 and v = 0, -1, -3, 10. The range of u is 7 - (-1) = 8. The range of v is 10 - (-3) = 13. The maximum is 13. The brute force also gives 13, from the pair (-2, 1) and (5, -5).

Note the tempting wrong answer. If you take the larger of the coordinate ranges, which is the Chebyshev distance (the larger of |dx| and |dy| for each pair), you get max(7, 9) = 9 on this sample. That is not the Manhattan answer, and the rotation is what changes the shape of the box.

Floating point where it cannot be avoided

Floating point appears in two places in this lesson: printing a decimal value, and rotating by an angle that is not a multiple of 90 degrees with cos and sin. The program below shows what each does on a machine with IEEE double precision, which almost every compiler uses.

// float_demo.cpp: where doubles go wrong on integer geometry.
#include <cstdio>
#include <cmath>
#include <cstdint>
 
int main() {
    // Part 1: rotate (1, 0) by 45 degrees twice. The true answer is (0, 1).
    double c = cos(M_PI / 4), s = sin(M_PI / 4);
    double x1 = 1 * c - 0 * s, y1 = 1 * s + 0 * c;     // after one rotation
    double x2 = x1 * c - y1 * s, y2 = x1 * s + y1 * c; // after two rotations
    printf("rotate twice: x = %.17g, y = %.17g\n", x2, y2);
    printf("x == 0 exactly? %s, y == 1 exactly? %s\n", x2 == 0.0 ? "yes" : "no", y2 == 1.0 ? "yes" : "no");
 
    // Part 2: line x + y = c with c = v, circle centred at the origin with radius r.
    // v^2 - 2 r^2 = 1 (Pell equation), so the distance v / sqrt(2) is just above r.
    // The exact answer is NONE (the line misses the circle). The gap is about 0.25 / r.
    long long v = 768398401LL, r = 543339720LL;
    long long exact = v * v - 2 * r * r;                 // fits in 64 bits: v^2 is about 5.9e17
    printf("exact v^2 - 2 r^2 = %lld, so the distance is above r by about %.3g\n", exact, 0.25 / (double)r);
    double dist = fabs((double)v) / sqrt(2.0);
    printf("double distance = %.17g\n", dist);
    printf("double r        = %.17g\n", (double)r);
    printf("double dist - r = %.17g\n", dist - (double)r);
    double eps = 1e-9;
    printf("tolerance 1e-9 says: %s\n", fabs(dist - r) < eps ? "TANGENT (wrong)" : (dist < r ? "TWO POINTS (wrong)" : "NONE"));
    // The squared form in doubles fails too: v^2 is above 2^53, so it is rounded.
    double sq = (double)v * (double)v - 2.0 * (double)r * (double)r;
    printf("squared form in double = %.1f (exact value is 1)\n", sq);
    return 0;
}

Its real output on the lesson machine:

rotate twice: x = 2.2204460492503131e-16, y = 1
x == 0 exactly? no, y == 1 exactly? yes
exact v^2 - 2 r^2 = 1, so the distance is above r by about 4.6e-10
double distance = 543339720
double r        = 543339720
double dist - r = 0
tolerance 1e-9 says: TANGENT (wrong)
squared form in double = 0.0 (exact value is 1)
NONE

The last line NONE is the exact test from transforms line on the same input 1 1 768398401 0 0 543339720, which gives the right answer.

Read the output carefully. The rotated x is 2.2e-16, not zero, because cos(pi/4) is stored with an error in its last bit. The test x == 0 therefore fails, even though the true value is zero. The near-tangent circle is a stronger example. The true distance from the centre to the line is above the radius by about 4.6e-10. A double holds about 16 significant digits, and at magnitude 5.4e8 the spacing between neighbouring doubles is about 1.2e-7, which is far larger than that gap. The distance is stored as exactly 543339720, equal to the radius, so the double test reports a touch.

Choosing a tolerance. There is no safe universal eps. A tolerance of 1e-9 works when the values being compared are of size one and the true gaps are much larger than 1e-9. Here the gap is 4.6e-10 at magnitude 5e8, so no absolute tolerance of this size can separate the cases. The workable rule is to avoid the comparison altogether, by squaring and staying in integers, as the exact program does. When floats are unavoidable, measure the smallest gap your inputs can produce, using a case like this one, and set the tolerance from that measurement. A relative tolerance (a fixed fraction of the magnitudes) is better than an absolute one, and a double-precision computation still needs care near the rounding limit.

Floating point is unavoidable for an actual rotation by an arbitrary angle, and for printing a distance. In those places, compute as late as possible, keep the exact integer form for every decision, and print with enough digits for the judge to check.

Hands-on exercise

Work on your own machine. Save the three programs from this lesson as circles.cpp, transforms.cpp and manhattan45.cpp, and compile each with g++ -O2 -std=c++17 -Wall -Wextra -o circles circles.cpp, and so on. Run them on the sample inputs in this lesson and check that you get the outputs shown above.

Then write an independent check for the circle counter. The Python program below classifies each pair with floating point and a tolerance. Small coordinates make the tolerance safe, so the float answer is trustworthy here, which it would not be for the near-tangent case above. It runs 300 random sets through ./circles and reports the mismatches. Your output should be mismatches: 0.

import math
import random
import subprocess
 
 
def classify_float(a, b, eps=1e-9):
    d = math.hypot(a[0] - b[0], a[1] - b[1])
    r1, r2 = a[2], b[2]
    if d < eps and abs(r1 - r2) < eps:
        return 3
    if abs(d - (r1 + r2)) < eps or abs(d - abs(r1 - r2)) < eps:
        return 1
    if d > r1 + r2 + eps or d < abs(r1 - r2) - eps:
        return 0
    return 2
 
 
random.seed(3)
bad = 0
for trial in range(300):
    n = random.randint(1, 12)
    cs = [(random.randint(-8, 8), random.randint(-8, 8), random.randint(1, 6)) for _ in range(n)]
    want = [0, 0, 0]
    for i in range(n):
        for j in range(i + 1, n):
            k = classify_float(cs[i], cs[j])
            if k == 2:
                want[0] += 1
            elif k == 1:
                want[1] += 1
            elif k == 3:
                want[2] += 1
    text = f"{n}\n" + "".join(f"{x} {y} {r}\n" for x, y, r in cs)
    out = subprocess.run(["./circles"], input=text, capture_output=True, text=True, check=True).stdout
    got = [int(v) for v in out.split()]
    if got != want:
        bad += 1
print("mismatches:", bad)

Last, try the rotation with your own numbers. Rotate (1, 0) by 45 degrees twice with cos and sin in your language, and print the result with enough digits to see the error. Then do the same with the integer map (x, y) -> (x - y, x + y) applied twice to (1, 0). Each step scales lengths by sqrt(2), so after two steps the point is (0, 2) exactly, with no rounding. Write one sentence on why the integer version is the one to trust when you test for equality. The float answer will differ in its last digits on other machines, so report what you see, not the numbers in this lesson.

Common mistakes

Testing tangency with a float and eps. The float_demo output above shows the symptom: TANGENT (wrong) for a line that misses the circle by 4.6e-10. The fix is the squared integer test in transforms line, which reports NONE.

Testing a rotated coordinate for equality. x == 0 fails for 2.2e-16. Rotate only by multiples of 90 degrees with integers, or compare with a tolerance that you justified from the inputs.

Overflow in a 32-bit int. A squared difference of coordinates near 10^6 reaches 4 * 10^12, which a 32-bit int cannot hold. Use long long for squared distances and __int128 for products of three terms, such as the circle-line test.

Counting identical circles as tangent or crossing. For identical circles, d2 is zero and t is zero, so the tangent test d2 == t*t is true and the pair is counted as tangent, which is wrong. The reference checks identical circles first and counts them separately.

Assuming every three points have a circumcircle. Collinear points have D = 0. The program prints COLLINEAR, no circumcircle for (0, 0), (1, 1), (2, 2), which is the expected result, and a solution that divides by D anyway prints garbage.

Printing fractions with a negative denominator. The circumcircle code flips the sign of the denominator and the numerators together, so the printed denominator is positive. Without that step a reader sees -17 / -2 in one place and 19 / 2 in another and cannot compare them.

Using the Chebyshev box instead of the rotation for Manhattan distance. On the sample, the larger coordinate range is 9, and the correct Manhattan answer is 13. The coordinate box and the rotated box are different shapes.

Checklist

Keep inputs as integers, and compare squares of distances and radii.
For circles, check identical, tangent and nested cases before the two-point case.
For a line and a circle, compare v*v with r*r*(a*a + b*b), using __int128 for large inputs.
For the circumcentre, check D for zero first, and keep the centre as a fraction.
Use (x + y, x - y) for the Manhattan problem, and compare the ranges of the two new coordinates.
Use floating point only for printing or for angles that are not multiples of 90 degrees.
If a float comparison is unavoidable, measure the smallest gap your inputs can produce and set the tolerance from it.
Test the program against a float version with a tolerance on small inputs, where the floats are reliable, and against a Fraction version on random inputs.

Summary

Circle and line tests become exact once they are written as comparisons of squares of integers. The circumcentre is a fraction with a known denominator, and the transforms that keep integers (translation, reflection, rotation by 90 degrees, and the rotation by 45 degrees in the form (x + y, x - y)) need no floating point at all. Floats belong to printing and to irrational angles, and any tolerance you use should come from the gap your inputs can produce, not from a habit of writing 1e-9.

Practice

Practice 1: count the circles

Given the circles (0, 0, 5), (3, 4, 5), (10, 0, 5) and (0, 0, 5), give the three output numbers of the circle counting problem.

Hint: compute d2 for each pair. Two of the pairs have equal radii, and one of them is identical.

Show the answer

Label the circles A (0,0,5), B (3,4,5), C (10,0,5) and D (0,0,5). A and B have d2 = 25, which lies strictly between (r1 - r2)^2 = 0 and (r1 + r2)^2 = 100, so they cross at two points. A and C have d2 = 100 = (r1 + r2)^2, so they touch (tangent). A and D are identical. B and C have d2 = 49 + 16 = 65, which lies strictly between 0 and 100, so they cross at two points. B and D have d2 = 25, so they cross at two points. C and D have d2 = 100, so they touch. The output is 3, 2, 1.

Practice 2: tangent or not

Decide with the squared test whether the line 3x + 4y = 25 touches the circle with centre (0, 0) and radius 5. Then decide for the line 3x + 4y = 26.

Hint: v = a*p + b*q - c with p = q = 0, so v = -c. Compare v*v with r*r*(a*a + b*b), which is 25 * 25 = 625.

Show the answer

For c = 25, v*v = 625 equals 625, so the line is tangent. For c = 26, v*v = 676 is greater than 625, so the line misses the circle. The distance 25 / 5 = 5 in the first case and 26 / 5 = 5.2 in the second confirms the same result without a square root.

Practice 3: circumcentre by hand

Find the circumcentre of (0, 0), (4, 0) and (0, 2). Give the centre as a pair of fractions and the squared radius.

Hint: the centre lies on the perpendicular bisector of the segment from (0, 0) to (4, 0), so its x coordinate is 2. Then find y from the distance to (0, 0).

Show the answer

The x coordinate is 2. The distance squared from (2, y) to (0, 0) is 4 + y*y, and to (0, 2) it is 4 + (y - 2)^2. Setting them equal gives y*y = y*y - 4y + 4, so y = 1. The centre is (2, 1) and the squared radius is 5. The formula gives the same result. Translate so that A is the origin, so B = (4, 0) and C = (0, 2). Then |B|^2 = 16, |C|^2 = 4 and D = 2 * (4*2 - 0*0) = 16. So ux = (2*16 - 0*4) / 16 = 2 and uy = (4*4 - 0*16) / 16 = 1. The centre is (2, 1), matching the geometric check.

Practice 4: a point at the origin

Explain why the inversion program prints undefined at the origin and not a fraction, and what happens to the point (1, 0) under inversion.

Hint: the denominator of the inversion is x*x + y*y.

Show the answer

The denominator N = x*x + y*y is zero at the origin, so the division has no value. The point (1, 0) has N = 1, so it maps to itself. Points on the unit circle stay where they are, points inside move outward, and points outside move inward.

Practice 5: why 45 degrees

For the Manhattan problem, let the points be (0, 0), (1, 2) and (-3, 1). Compute the answer with the rotation and then check it with the three pairwise distances.

Hint: compute u = x + y and v = x - y for each point, then take the two ranges.

Show the answer

The values are u = 0, 3, -2 and v = 0, -1, -4. The range of u is 3 - (-2) = 5 and the range of v is 0 - (-4) = 4, so the answer is 5. The pairwise Manhattan distances are |1| + |2| = 3 for (0,0) and (1,2), |3| + |1| = 4 for (0,0) and (-3,1), and |-4| + |-1| = 5 for (1,2) and (-3,1). The largest is 5, which agrees.