#!/usr/bin/env python3
"""Independent exact recheck for no-four-on-a-circle certificates (director, 2026-10-02; shares no code with check.py).

A set S of points of the n x n grid has no four points on a common circle or line iff for every 4-subset the integer
determinant det[[x, y, x^2 + y^2, 1]] is nonzero (it vanishes exactly when the four points are concyclic or collinear).
Checks: integer coordinates, distinct points, both coordinate spans <= n - 1 (fits an n x n grid), |S| = k, all 4-subsets.
Usage: recheck_circ.py CERT.json K   (exit 0 = valid, 1 = invalid). Standard library only.
"""
import itertools, json, sys

def det4(rows):
    # Laplace expansion on the last column (all ones), exact integers.
    def det3(m):
        (a, b, c), (d, e, f), (g, h, i) = m
        return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)
    total = 0
    for r in range(4):
        minor = [row[:3] for j, row in enumerate(rows) if j != r]
        total += (-1) ** (r + 3) * det3(minor)
    return total

def check(points, n, k):
    if not all(isinstance(c, int) for p in points for c in p) or any(len(p) != 2 for p in points):
        return "non-integer or malformed point"
    if len(set(map(tuple, points))) != len(points):
        return "repeated point"
    xs, ys = [p[0] for p in points], [p[1] for p in points]
    if max(xs) - min(xs) > n - 1 or max(ys) - min(ys) > n - 1:
        return "does not fit an n x n grid"
    if len(points) != k:
        return f"size {len(points)} != {k}"
    rows = [(x, y, x * x + y * y, 1) for x, y in points]
    for q in itertools.combinations(range(len(rows)), 4):
        if det4([rows[i] for i in q]) == 0:
            return "four on a circle or line: " + str([points[i] for i in q])
    return None

def main(argv):
    cert = json.load(open(argv[1])); k = int(argv[2])
    err = check([list(p) for p in cert["points"]], int(cert["n"]), k)
    print(("INVALID: " + err) if err else f"VALID n={cert['n']} k={k} ({len(cert['points'])} points, all 4-subsets nonzero)")
    return 1 if err else 0

if __name__ == "__main__":
    sys.exit(main(sys.argv))