hexagonal rows as an alternative lattice; pick the better derived radius

-"""Baseline: a lattice of candidate points inside the container, spacing found by bisection so
-that at least n fit. Deliberately naive; scores well below the records. Beat it."""
 
-import itertools
 import math
 
-DIM = 2
-
-
-def _boundary(c):
-    return min(c[0], 1 - c[0], c[1], 1 - c[1])
-
-
-def _weight(i):
-    return 1.0
-
+def _radius(pts):
+    r = min(min(x, 1 - x, y, 1 - y) for x, y in pts)
+    n = len(pts)
+    for i in range(n):
+        xi, yi = pts[i]
+        for j in range(i + 1, n):
+            d = math.hypot(xi - pts[j][0], yi - pts[j][1]) / 2
+            if d < r:
+                r = d
+    return r
 
-def _lattice(n, r):
-    """Cubic lattice points at spacing 2r whose distance to the boundary is at least r."""
-    lo, hi = ((0.0,) * DIM, (1.0,) * DIM)
-    step = 2.0 * r
-    axes = []
-    for d in range(DIM):
-        k = int((hi[d] - lo[d]) / step) + 1
-        axes.append([lo[d] + r + i * step for i in range(k)])
-    pts = [p for p in itertools.product(*axes) if _boundary(p) >= r]
-    return pts
+def _grid(n):
+    best = None
+    for rows in range(1, n + 1):
+        cols = math.ceil(n / rows)
+        m = max(rows, cols)
+        if best is None or m < best[0]:
+            best = (m, rows, cols)
+    m, rows, cols = best
+    step = 1.0 / m
+    return [((j + 0.5) * step, (i + 0.5) * step) for i in range(rows) for j in range(cols)][:n]
 
+def _hex(n):
+    best = None
+    for rows in range(1, n + 1):
+        for cols in range(1, n + 1):
+            count = rows * cols - rows // 2
+            if count < n:
+                continue
+            r = min(1.0 / (2 * cols), 1.0 / (2 + (rows - 1) * math.sqrt(3)))
+            if best is None or r > best[0]:
+                best = (r, rows, cols)
+    r, rows, cols = best
+    pts = []
+    for i in range(rows):
+        k = cols - (i % 2)
+        for j in range(k):
+            pts.append((r + (i % 2) * r + 2 * r * j, r + i * r * math.sqrt(3)))
+    return pts[:n]
 
 def pack(n, time_budget, seed):
-    # treat every object as the largest one when choosing the lattice spacing
-    wmax = max(_weight(i + 1) for i in range(n))
-    # find a feasible spacing by halving, then bisect between it and the last infeasible one
-    a = 1.0
-    while len(_lattice(n, a * wmax)) < n and a > 1e-9:
-        a /= 2
-    b = 2 * a
-    for _ in range(40):
-        m = (a + b) / 2
-        if len(_lattice(n, m * wmax)) >= n:
-            a = m
-        else:
-            b = m
-    pts = _lattice(n, a * wmax)
-    pts.sort(key=lambda p: -_boundary(p))   # keep the most interior points
-    return [tuple(p) for p in pts[:n]]
+    cands = [_grid(n), _hex(n)]
+    return max(cands, key=_radius)