"""Validate a packing of n unit squares (possibly rotated) in the container [0, side]^2.

Exact mode: side and every coordinate are Fraction/int and each direction (c, s)
satisfies c^2 + s^2 == 1 exactly (axis-aligned, or Pythagorean like 3/5, 4/5).
Then the verdict is a proof (eps = 0, no tolerance).
Float mode: verdict means "valid within eps"; NOT a proof. Worst violations are reported.
"""
from __future__ import annotations
from dataclasses import dataclass
from fractions import Fraction
import math

Num = object  # Fraction | int | float


@dataclass(frozen=True)
class Sq:
    x: Num  # center x
    y: Num  # center y
    c: Num  # cos(rotation)
    s: Num  # sin(rotation)


def _is_exact(v) -> bool:
    return isinstance(v, (Fraction, int)) and not isinstance(v, bool)


def _radius(u, q: Sq):
    """Half-extent of unit square q (edge dirs (c,s), (-s,c)) projected on unit axis u."""
    ux, uy = u
    return (abs(ux * q.c + uy * q.s) + abs(-ux * q.s + uy * q.c)) / 2


def penetration(a: Sq, b: Sq):
    """Min overlap depth over the 4 separating axes. >0: interiors overlap; <=0: apart/touching."""
    dx, dy = b.x - a.x, b.y - a.y
    axes = ((a.c, a.s), (-a.s, a.c), (b.c, b.s), (-b.s, b.c))
    return min(_radius(u, a) + _radius(u, b) - abs(dx * u[0] + dy * u[1]) for u in axes)


def outside_amount(q: Sq, side):
    """How far q sticks out of [0, side]^2. <= 0 means inside."""
    h = (abs(q.c) + abs(q.s)) / 2
    return max(h - q.x, q.x + h - side, h - q.y, q.y + h - side)


def validate(squares, side, eps=None, expected_n=None, max_report=10):
    n = len(squares)
    exact = _is_exact(side) and all(_is_exact(v) for q in squares for v in (q.x, q.y, q.c, q.s))
    if exact:  # normalise ints to Fraction so all arithmetic stays rational
        side = Fraction(side)
        squares = [Sq(*(Fraction(v) for v in (q.x, q.y, q.c, q.s))) for q in squares]
    if eps is None:
        eps = Fraction(0) if exact else 1e-9
    one = Fraction(1) if exact else 1.0
    unit_tol = 0 if exact else 1e-9
    bad, issues = 0, []

    def flag(msg):
        nonlocal bad
        bad += 1
        if len(issues) < max_report:
            issues.append(msg)

    if expected_n is not None and n != expected_n:
        flag(f"expected {expected_n} squares, got {n}")
    for i, q in enumerate(squares):
        if abs(q.c * q.c + q.s * q.s - one) > unit_tol:
            flag(f"square {i}: (c, s) is not a unit vector")

    max_outside = 0
    for i, q in enumerate(squares):
        o = outside_amount(q, side)
        if o > eps:
            flag(f"square {i}: outside container by {float(o):.3e}")
        max_outside = max(max_outside, o)

    max_overlap = 0
    order = sorted(range(n), key=lambda i: squares[i].x)
    for pos, i in enumerate(order):
        a = squares[i]
        for j in order[pos + 1:]:
            b = squares[j]
            dx = b.x - a.x  # >= 0 by sort
            if dx * dx > 2:  # circumradius sqrt(2)/2 each -> no overlap possible for rest
                break
            dy = b.y - a.y
            if dx * dx + dy * dy > 2:
                continue
            p = penetration(a, b)
            if p > eps:
                flag(f"squares {i},{j}: overlap depth {float(p):.3e}")
            max_overlap = max(max_overlap, p)

    return {"valid": bad == 0, "mode": "exact" if exact else f"float(eps={eps})",
            "proof": exact and bad == 0, "n": n, "max_overlap": float(max_overlap),
            "max_outside": float(max_outside), "violations": bad, "issues": issues}


def parse_squares(items):
    """items: list of dicts, one form for all squares.
    Exact:  {"x","y","c","s"} as ints/strings like "3/5".
    Float:  {"x","y","theta_rad"} or {"x","y","theta_deg"} (unit must be explicit; we never guess)."""
    if not items:
        return []
    if all("c" in d and "s" in d for d in items):
        return [Sq(*(Fraction(str(d[k])) for k in ("x", "y", "c", "s"))) for d in items]
    for key, conv in (("theta_rad", float), ("theta_deg", lambda v: math.radians(float(v)))):
        if all(key in d for d in items):
            out = []
            for d in items:
                t = conv(d[key])
                out.append(Sq(float(d["x"]), float(d["y"]), math.cos(t), math.sin(t)))
            return out
    raise ValueError("use c/s, theta_rad, or theta_deg consistently for all squares")