# Exact upper bound for the distortion of a closed polygon with integer vertices.
# Author: David Niedbala Giraudin, ORCID 0009-0009-1526-1178
# Technical assistance: Claude (Anthropic)
#
# distortion(F) = sup_{p != q} d_F(p,q) / |p - q|, d_F = length of the shorter arc.
# For each pair of edges (e_i, e_j) we prove ratio <= D:
#  - same edge: ratio = 1;
#  - adjacent edges with common vertex V: sup = 1/sin(phi/2), phi the angle at V between the
#    two edges (points at distances x, y from V: arc <= x + y, chord squared = x*x + y*y - 2xy cos phi);
#  - other pairs: subdivide (s,t) in the unit square into dyadic boxes; on a box the shorter arc is at
#    most min(max a1, max a2) (affine, evaluated with rational upper bounds of edge lengths)
#    and the chord is at least the exact distance between the two sub-segments.
from fractions import Fraction as Fr
from math import isqrt

def dot(u, v): return u[0]*v[0] + u[1]*v[1] + u[2]*v[2]
def sub(u, v): return (u[0]-v[0], u[1]-v[1], u[2]-v[2])

def seg_dist2(P0, P1, Q0, Q1):
    """exact squared distance between segments [P0,P1] and [Q0,Q1] (rational points)."""
    d1 = sub(P1, P0); d2 = sub(Q1, Q0); r = sub(P0, Q0)
    a = dot(d1, d1); e = dot(d2, d2); f = dot(d2, r)
    def at(s, t):
        w = tuple(r[k] + s*d1[k] - t*d2[k] for k in range(3)); return dot(w, w)
    def clamp(x): return min(max(x, Fr(0)), Fr(1))
    cands = []
    # interior critical point
    c = dot(d1, r); b = dot(d1, d2); den = a*e - b*b
    if den != 0:
        s = Fr(b*f - c*e, den); t = Fr(a*f - b*c, den)
        if 0 <= s <= 1 and 0 <= t <= 1: cands.append(at(s, t))
    # edges of the parameter square
    for s in (Fr(0), Fr(1)):
        t = clamp(Fr(f + s*b, e)) if e else Fr(0); cands.append(at(s, t))
    for t in (Fr(0), Fr(1)):
        s = clamp(Fr(t*b - c, a)) if a else Fr(0); cands.append(at(s, t))
    return min(cands)

def length_bounds(n2):
    r = isqrt(n2)
    lo = Fr(r); hi = Fr(r if r*r == n2 else r + 1)
    return lo, hi

def certify(X, D, max_depth=40, verbose=False):
    """X: list of integer 3-tuples (closed polygon). D: Fraction. Returns (ok, stats)."""
    n = len(X)
    E = [sub(X[(k+1) % n], X[k]) for k in range(n)]
    # refined rational upper bounds of lengths: scale by 2**20 before isqrt
    SC = 1 << 20
    lhi = []
    for e in E:
        n2 = dot(e, e) * SC * SC
        r = isqrt(n2); lhi.append(Fr(r if r*r == n2 else r + 1, SC))
    tot = sum(lhi)
    pref = [Fr(0)]
    for x in lhi: pref.append(pref[-1] + x)
    D2 = D * D
    boxes = 0; deepest = 0
    for i in range(n):
        for j in range(i + 1, n):
            if j == i + 1 or (i == 0 and j == n - 1):
                if j == i + 1: V = X[j]; u = sub(X[i], V); v = sub(X[j+1 if j+1 < n else 0], V)
                else: V = X[0]; u = sub(X[1], V); v = sub(X[n-1], V)
                uv = dot(u, v)
                if uv > 0:
                    lhs = (D2 - 2) ** 2 * dot(u, u) * dot(v, v); rhs = D2 * D2 * uv * uv
                    if not (D2 > 2 and lhs >= rhs):
                        return False, ("adjacent", i, j)
                continue
            mid1 = pref[j] - pref[i+1]            # edges strictly between i and j (forward)
            mid2 = tot - pref[j+1] + pref[i]      # edges outside [i, j]
            stack = [(Fr(0), Fr(1), Fr(0), Fr(1), 0)]
            while stack:
                s0, s1, t0, t1, dep = stack.pop(); boxes += 1
                a1 = (1 - s0) * lhi[i] + mid1 + t1 * lhi[j]
                a2 = s1 * lhi[i] + mid2 + (1 - t0) * lhi[j]
                am = min(a1, a2)
                P0 = tuple(X[i][k] + s0*E[i][k] for k in range(3)); P1 = tuple(X[i][k] + s1*E[i][k] for k in range(3))
                Q0 = tuple(X[j][k] + t0*E[j][k] for k in range(3)); Q1 = tuple(X[j][k] + t1*E[j][k] for k in range(3))
                d2 = seg_dist2(P0, P1, Q0, Q1)
                if D2 * d2 >= am * am: continue
                if dep >= max_depth: return False, ("depth", i, j, float(s0), float(t0))
                deepest = max(deepest, dep + 1)
                sm = (s0 + s1) / 2; tm = (t0 + t1) / 2
                stack += [(s0, sm, t0, tm, dep+1), (sm, s1, t0, tm, dep+1), (s0, sm, tm, t1, dep+1), (sm, s1, tm, t1, dep+1)]
        if verbose and i % 10 == 0: print("  edge", i, "boxes", boxes, flush=True)
    return True, {"boxes": boxes, "depth": deepest}