100,000 Packed Squares

Submit one binary .sqp file. It contains exactly 100,000 square placements. Each placement is a center (x, y) and a rotation theta in radians.

The file is exactly 2,400,016 bytes:

bytes 0..4       magic: the 4 ASCII bytes "SPN1"
bytes 4..8       count: u32 little-endian, exactly 100000
byte  8          decimal places: exactly 16
bytes 9..16      seven zero bytes
then exactly 100,000 records, each 24 bytes:
    bytes 0..8   X: u64 little-endian
    bytes 8..16  Y: u64 little-endian
    bytes 16..24 T: u64 little-endian

The placement is x = X / 10^16, y = Y / 10^16, and theta = T / 10^16. The format accepts 0 <= x,y < 317 and 0 <= theta < pi/2; records may be in any order. There is no padding or trailing data. The enclosing square is calculated from the edges of all squares, so center coordinates alone do not define it.

To encode a CSV with x,y,theta columns:

python3 tools/sqp.py encode placements.csv solution.sqp
python3 tools/sqp.py inspect solution.sqp

generate-baseline, decode, and validate are also available through tools/sqp.py --help.

A submission is valid only if all of these hold:

1. It is one exactly 2,400,016-byte .sqp file containing exactly 100,000 placements.
2. Every position and angle is within the ranges defined in What you submit.
3. Square interiors are pairwise disjoint. Edge and point contact are allowed when the verifier can establish that they do not overlap.

For rotated squares, the verifier does not use a tolerance. If a submission relies on a contact so exact that the verifier cannot determine whether the interiors overlap, it is invalid. Leave a small positive gap rather than relying on an exact rotated contact.

Scores use two metrics, ranked lexicographically:

1. Side length (minimize): the enclosing side rounded upward to eight decimal places.
2. Rotated squares (minimize): the number of placements with a nonzero stored angle.

The displayed side always has eight decimal places. The reference grid scores 317.00000000 with zero rotated squares.

A new submission takes the record when it has a smaller side length or, at the same side length, uses fewer rotated squares.

The verifier also reports the number of distinct angles for context. This value does not affect ranking.

The verifier reads the exact binary format, checks every field, proves that square interiors do not overlap, and computes the enclosing side. It is the specification.

It uses exact integer arithmetic for axis-aligned squares and certified interval arithmetic for rotated geometry. Collision checks use nearby coordinate buckets, then the separating-axis test on both squares. Comparisons begin at 160-bit precision and may increase through 320, 640, 1,280, and 2,048 bits. An unresolved comparison is invalid; no floating-point tolerance is used.

Duplicate detection uses a verifier-owned fingerprint. It ignores record order, global translation, and quarter turns. For fully axis-aligned placements it also ignores reflections. Malformed files receive a raw-byte fingerprint and are invalid.

The repository contains a readable Python verifier and a Rust verifier used by the Docker image. They are tested against the same fixtures and must agree on validity, metrics, and fingerprints.