{"id":"circle-packing-rectangle-600","name":"Equal circles in a 1 × 0.6 rectangle","family":"combinatorics","description":"Place n circles in the rectangle [0, 1] × [0, 0.6] as large as possible (equal). Scored against the best-known Packomania records; anything above 1.0 on an n is a new record candidate.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":600,"agent_timeout_seconds":1800,"mutable":["pack.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Equal circles in a 1 × 0.6 rectangle\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, ...]]`: the\ncentres of `n` circles inside the rectangle [0, 1] × [0, 0.6] (2 coordinates each). All objects share one radius, which the eval derives as\n\n    r = min( distance of every centre to the boundary, half the smallest pairwise distance )\n\nYou do not return a radius; the eval derives the largest feasible one from your centres, so there\nis nothing to fudge. Make it as large as possible for every `n` you are handed.\n\n## Metric\n\nThe eval runs your `pack` on a fixed set of values, `n = 8, 13, 19, 26, 31, 37, 44, 52, 68, 85, 101, 120, 150, 200`, each with the given time\nbudget (12 s by default), validates the result, and reports\n\n    metric = mean over n of  value(n) / record(n)\n\nwhere `record(n)` is the best-known value on Packomania (Eckard Specht's table, maintained since\n2011; table `crc_600`, fetched 2026-09-06). `1.0` matches the record; above `1.0` is a new record\ncandidate, listed under `records_beaten`. A hub-verified one is worth reporting to Packomania\nwith your ledger entry as provenance.\n\nThe hub verifies with a different `seed`, so your method must be robust to its starting point.\nThe full records table (n up to 307) is in `eval.py`.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no subprocess. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval kills the run if the whole set overruns.\n- Deterministic given `seed`: use `random.Random(seed)`, not the global RNG.\n- Every centre must lie inside the container. Objects may touch; they may not overlap.\n\n## Where the frontier is\n\nonly small n are proven. Above that every entry is \"best known\", found by numerical search, and Packomania's\nhistory shows improvements landing mostly at larger `n`. Budget your time per `n` deliberately;\nthe O(n²) checks and the number of local optima both grow.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Energy minimisation: treat objects as repelling points, minimise a soft overlap penalty with\n  gradient descent, then polish by maximising the minimum scaled distance directly.\n- Basin hopping / perturb-and-repolish from the current best; keep a small population.\n- Start from structured arrangements (lattices, rings, shells) as well as random.\n- Identify the binding contacts and solve the equal-distance conditions exactly for the last digits.\n- Spend more of the budget on the `n` values whose ratio is lowest.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for circle-packing-rectangle-600. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/crc_600/crc.html on 2026-09-06.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to pack() (the n set is fixed so scores are comparable)\n  ZT_EVAL_NS               comma-separated n values (default \"8,13,19,26,31,37,44,52,68,85,101,120,150,200\")\n  ZT_EVAL_PER_N_SECONDS    time budget handed to pack() per n (default 12)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport itertools\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"8,13,19,26,31,37,44,52,68,85,101,120,150,200\").split(\",\")]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"12\"))\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nDIM = 2\n\n# Best-known values: equal objects in the rectangle [0, 1] × [0, 0.6]. Source: Packomania (E. Specht),\n# https://packomania.com/crc_600/crc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.300000000000000000000000000000, 2: 0.252277442494833886543030217200, 3: 0.190033112945850060552663038611, 4: 0.170148518491376613990984224879, 5: 0.161906968533948391953240608944,\n    6: 0.152859547920896831706610375860, 7: 0.138202193662700008063251246929, 8: 0.129823202479241967529606948497, 9: 0.119859330293026045975108487226, 10: 0.115181843761790566266666927050,\n    11: 0.113391171522144578074331661858, 12: 0.110087864570056706926546414921, 13: 0.103387978507317515916280049437, 14: 0.101761192204379056241227668568, 15: 0.100000000000000000000000000000,\n    16: 0.093797838338222718713266723881, 17: 0.090595211729214143885671491673, 18: 0.088816840445305969363688135661, 19: 0.086139465043560085744089332046, 20: 0.085313228856734899660154480474,\n    21: 0.083632003811217052960148270432, 22: 0.083333390926571692920705530966, 23: 0.080963851409875205430096646174, 24: 0.078738362897184921216107645667, 25: 0.076111210904624479971168700325,\n    26: 0.075269601455117943710372487386, 27: 0.074365852672261350381143856416, 28: 0.072185619195103696372984993568, 29: 0.071013064611104942093870916333, 30: 0.069873184169852096555429375186,\n    31: 0.068983877503286077022884143746, 32: 0.068531951302623509104816842223, 33: 0.068238280906633925850685147161, 34: 0.067224848345629393909876512775, 35: 0.066777988620622636333178554191,\n    36: 0.064864187234285720686962087628, 37: 0.063795381290717125360470501751, 38: 0.063164281791970610657152125222, 39: 0.062549676213039062207347093133, 40: 0.060979899611387310535536259518,\n    41: 0.060365631801331908669269450468, 42: 0.060050889756071894912618890029, 43: 0.059249487499123673151910721080, 44: 0.058460541101100379843314762725, 45: 0.058007177883918538361817486879,\n    46: 0.057373989202189921721680286809, 47: 0.057130592273447163141442690262, 48: 0.056939492662112365819745661873, 49: 0.056298951605230106563868615085, 50: 0.055830318092897474239042328996,\n    51: 0.055583903409206094373719803296, 52: 0.055040033495100533998187846034, 53: 0.053790817406067476784201543400, 54: 0.053311482080480786983761514150, 55: 0.052616338387560684439075272058,\n    56: 0.052137768714640547575382499042, 57: 0.051582534356042388682237612219, 58: 0.051237910320536906490482141180, 59: 0.050706174315801995478246356597, 60: 0.050553432731854556955008670987,\n    61: 0.050182346715695772179223575945, 62: 0.050019265294996293430818188740, 63: 0.049588519874224096144942710287, 64: 0.049178971206793468597089855416, 65: 0.048996637465208928326848777752,\n    66: 0.048877198579304509519441441418, 67: 0.048808032286899533489909394351, 68: 0.048203585880325583732822235349, 69: 0.047936328230153371927565323054, 70: 0.047738743414358588960235352626,\n    71: 0.046845939657103390984717011752, 72: 0.046454400273506725972324693338, 73: 0.046115119350366066638652143470, 74: 0.045943929309031043069390760402, 75: 0.045529788975339611234628761837,\n    76: 0.045062666008299022987615217020, 77: 0.044832403115893020873674900225, 78: 0.044593362449119819230429272407, 79: 0.044210741815710147985137170899, 80: 0.044024472311550027429922689820,\n    81: 0.043770785252999991499400659697, 82: 0.043622023044679100922527684288, 83: 0.043400610809484700317996902222, 84: 0.043305433574897591283199039157, 85: 0.042982324827260661373803909779,\n    86: 0.042857267414152390057784885164, 87: 0.042772277821076229840796827272, 88: 0.042734604206597389425263933056, 89: 0.042391428293754711239213251551, 90: 0.042044712409535343135846332539,\n    91: 0.041823077456194908129888354384, 92: 0.041724924554608747131330656711, 93: 0.041666672490105979936457489951, 94: 0.040837872228762735480219514075, 95: 0.040614330036223259545060730052,\n    96: 0.040464655607444877605067759248, 97: 0.040222406127193383326113173166, 98: 0.040145258829918742473304634167, 99: 0.039705133723128588452475142309, 100: 0.039601343582990219035127383959,\n    101: 0.039395550373002270829281261777, 102: 0.039219929578305156839739422587, 103: 0.039024466504370088593760029126, 104: 0.038824656938777344709555126466, 105: 0.038695258580272363135736101717,\n    106: 0.038591710769278615170651086770, 107: 0.038465300822719144657169962077, 108: 0.038436768318894983827801838815, 109: 0.038161714003952677975162625306, 110: 0.038072360058739145232236021172,\n    111: 0.038049094852954012781849863304, 112: 0.038015912104341849825999159480, 113: 0.037992860696830608783020003566, 114: 0.037644408547753311119541989070, 115: 0.037363867647885350339594772989,\n    116: 0.037230168485884040237819061331, 117: 0.037131308721004909317314016113, 118: 0.036698886764217093168933752324, 119: 0.036476444068007089709547099981, 120: 0.036290083585114096902612492052,\n    121: 0.036207859355308014814897247452, 122: 0.036070333100163751699094648406, 123: 0.035842470183765791375281322662, 124: 0.035653641555662961401830719874, 125: 0.035551647694401039812005557853,\n    126: 0.035468718119521284135424937731, 127: 0.035407730637512828290468244251, 128: 0.035366537453999741400704335201, 129: 0.035019926001753872856333353554, 130: 0.034988991949928848400978368331,\n    131: 0.034816261951563169578967496568, 132: 0.034738961664461883772389843411, 133: 0.034703820292364330195742789904, 134: 0.034575768752801840849303857736, 135: 0.034553219759794081253661293713,\n    136: 0.034361179216360126382916849962, 137: 0.034300868397485173257673891079, 138: 0.034243125032239252670297028295, 139: 0.034218031188992641572308503719, 140: 0.034205856530511793869479645526,\n    141: 0.033857171698861394672044431856, 142: 0.033725962961206872613478873857, 143: 0.033604127826936151415528929275, 144: 0.033456804442313945412156267023, 145: 0.033400919531632180194292724313,\n    146: 0.033342677786254706072396413244, 147: 0.032899698280410432017543860083, 148: 0.032783402189623942329709396078, 149: 0.032672625004985094101797681912, 150: 0.032643080281879979247158115096,\n    151: 0.032437263015501888043455117983, 152: 0.032317232929172710210326734728, 153: 0.032309107846068971901921753277, 154: 0.032093377520621047433644727778, 155: 0.032003177974121316095029004046,\n    156: 0.031913949683438346230046057226, 157: 0.031878643189728845161112563121, 158: 0.031798677478125552084209082952, 159: 0.031740219573971966232601807368, 160: 0.031734370540692657588469771170,\n    161: 0.031629136778028430016117359109, 162: 0.031611447512215264292906835474, 163: 0.031437908021694459970211274607, 164: 0.031399636336131800414927385413, 165: 0.031383258293140119608506899287,\n    166: 0.031231674787779595772128702938, 167: 0.031199100069534795981712270054, 168: 0.031147565591920175424101572001, 169: 0.031120722699875756032307688712, 170: 0.031109780252290281448138197176,\n    171: 0.031102800122496892969604412239, 172: 0.030773291058771098926581659329, 173: 0.030640801929732220766681529960, 174: 0.030498465321491756162785466238, 175: 0.030432826197828666379088603770,\n    176: 0.030380795825634950192079479512, 177: 0.030166655873251916465427501311, 178: 0.030039846290078817263956174741, 179: 0.030000272979068800516719953962, 180: 0.030000272979068800516719953962,\n    181: 0.030000226677712598459585167344, 182: 0.029752980903883024637898701562, 183: 0.029618547047457066528623161349, 184: 0.029476593252140407964680593239, 185: 0.029411475086797224230592097577,\n    186: 0.029354052515907870376406975462, 187: 0.029288759450674240041045764092, 188: 0.029242609853932227758256291952, 189: 0.029140407586418325645616141542, 190: 0.029064406954861338197549243594,\n    191: 0.029043049677999418749535065438, 192: 0.029034503453100587675653471587, 193: 0.028926682864779503049263121971, 194: 0.028861425173095472286448201439, 195: 0.028839849620386961911693258314,\n    196: 0.028784308322136055936974351371, 197: 0.028752428293042451270820292199, 198: 0.028746747756599330016685860528, 199: 0.028621495111403511816937200188, 200: 0.028592689891498870215136720450,\n    201: 0.028550338789768405336245622430, 202: 0.028531227701887814962601307444, 203: 0.028520073423883192537383835665, 204: 0.028517581613553785630714390249, 205: 0.028184286775978505185322449229,\n    206: 0.028121608653889651458668982571, 207: 0.028053964475707300872224292977, 208: 0.027936329575554562043411809283, 209: 0.027899426265541834117009304486, 210: 0.027868986138080925704178616854,\n    211: 0.027803324263653919595083824932, 212: 0.027569811433140979162236606668, 213: 0.027487455252363550987319379193, 214: 0.027418806577034438364036871747, 215: 0.027366792506779333500379267039,\n    216: 0.027352575634240782131966383375, 217: 0.027272728372699205044366726436, 218: 0.027272728372699205044366726436, 219: 0.027272728372699205044366726436, 220: 0.027272728372699205044366726436,\n    221: 0.027272727272727272727272727273, 222: 0.026996864488041587146323501962, 223: 0.026925456281096396206893070772, 224: 0.026878316629862250905863629959, 225: 0.026830644902879938843983726418,\n    226: 0.026776122606057054291515816556, 227: 0.026759694099582265587435073720, 228: 0.026758678778625100265044658761, 229: 0.026616897020529773795639539749, 230: 0.026592914684728304739820681044,\n    231: 0.026579741997837480360698487099, 232: 0.026551161257434696835288218366, 233: 0.026521301330875501239439150406, 234: 0.026519477558941329798304799227, 235: 0.026420450838107652692899093626,\n    236: 0.026403219150426022091762586964, 237: 0.026374911915324439536483237516, 238: 0.026341892367063298285890044182, 239: 0.026329893757181922882057132581, 240: 0.026316315077810461265284077871,\n    241: 0.026315791718677725832493694701, 242: 0.026066919461668114918034711111, 243: 0.025941806510624237528211633542, 244: 0.025862851250391072802924742620, 245: 0.025784333219823765148774316987,\n    246: 0.025740817046143247064106917530, 247: 0.025725197994896957051141498281, 248: 0.025594025822939095618951477825, 249: 0.025513977635286375355705030910, 250: 0.025429796599605019771883183565,\n    251: 0.025402450167439768719927136472, 252: 0.025322161635267527760294136615, 253: 0.025306680671956082380880661164, 254: 0.025267550008597889812198213619, 255: 0.025194223148236117961715197518,\n    256: 0.025134991083437822013963070338, 257: 0.025083330693356314765760360106, 258: 0.025065013917735581561856169278, 259: 0.025063343097520921980991884631, 260: 0.024980368485814516639423857259,\n    261: 0.024962730170891139226673368749, 262: 0.024959387575023820377098831758, 263: 0.024956897424612416021867156603, 264: 0.024951687022049461416289131926, 265: 0.024951494899910413409794858690,\n    266: 0.024814260708845719648851572573, 267: 0.024743985816422562252806660977, 268: 0.024693893613377944518777023936, 269: 0.024675148375783687383342082385, 270: 0.024663645933318877272439541289,\n    271: 0.024628150570044006604522279226, 272: 0.024615796091601033413484158055, 273: 0.024613022353524666785338536812, 274: 0.024527073955751477836756397642, 275: 0.024514295683388060629347520244,\n    276: 0.024487995871768795652010723196, 277: 0.024453952060534108407806916906, 278: 0.024427388543216239266727956245, 279: 0.024403646363224419760997280708, 280: 0.024396401107903433891833839286,\n    281: 0.024164678171347686434629743016, 282: 0.024096775690898332048673899277, 283: 0.024057910218987999860065094460, 284: 0.024003624466759196859419163282, 285: 0.023948485224995422412492984848,\n    286: 0.023928224366071727631470662339, 287: 0.023928224255743220050441452954, 288: 0.023927751889555548089278808124, 289: 0.023725761205130319803546579242, 290: 0.023656117518829317675687674518,\n    291: 0.023599759793262936068619462341, 292: 0.023563466881362489276065869929, 293: 0.023535547828115300347485082499, 294: 0.023521522943535559824997292009, 295: 0.023500163555372985952056435514,\n    296: 0.023461206880485300286640076146, 297: 0.023405600922652805048250173422, 298: 0.023362017568086337936568413192, 299: 0.023346372477131727916619360498, 300: 0.023275893755896650785991783252,\n    301: 0.023236480482963347803747558402, 302: 0.023215425055959923683019565366, 303: 0.023200617088860396991193494332, 304: 0.023173681497999945436747130176, 305: 0.023157299062031371677388693317,\n    306: 0.023139834197111943590490737592, 307: 0.023134143833945586175676545278,\n}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in pack.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n\n\ndef boundary(c) -> float:\n    \"\"\"Distance from centre c to the container boundary; negative outside.\"\"\"\n    return min(c[0], 1 - c[0], c[1], 0.6 - c[1])\n\n\ndef weight(i: int) -> float:\n    \"\"\"Radius weight of object i (1-based); the eval derives the common scale s, r_i = weight(i) * s.\"\"\"\n    return 1.0\n\n\ndef value_of(centres: list, n: int) -> float:\n    if not isinstance(centres, (list, tuple)) or len(centres) != n:\n        fail(f\"pack({n}) must return {n} centres\", \"wrong_answer\")\n    pts = []\n    for c in centres:\n        try:\n            p = tuple(float(v) for v in c)\n        except Exception:\n            fail(f\"pack({n}) returned a non-point {c!r}\", \"wrong_answer\")\n        if len(p) != DIM or not all(math.isfinite(v) for v in p):\n            fail(f\"pack({n}) returned a point that is not {DIM}-D and finite: {c!r}\", \"wrong_answer\")\n        if boundary(p) < -EPS:\n            fail(f\"pack({n}) placed a centre outside the container: {p}\", \"wrong_answer\")\n        pts.append(p)\n    w = [weight(i + 1) for i in range(n)]\n    s = min(max(boundary(p), 0.0) / w[i] for i, p in enumerate(pts))   # upper bound from the walls\n    if s <= EPS:\n        fail(f\"pack({n}) has a centre on the boundary (scale={s})\", \"wrong_answer\")\n    # Any pair that limits the scale below s has distance < (w_i + w_j) s <= 2 wmax s, so it lies\n    # in the same or an adjacent cell of a grid with that spacing. Expected O(n) instead of O(n^2).\n    cell = 2.0 * max(w) * s\n    grid = {}\n    for idx, p in enumerate(pts):\n        key = tuple(int(math.floor(v / cell)) for v in p)\n        grid.setdefault(key, []).append(idx)\n    offsets = list(itertools.product((-1, 0, 1), repeat=DIM))\n    for key, members in grid.items():\n        for off in offsets:\n            nb = tuple(k + o for k, o in zip(key, off))\n            if nb < key or nb not in grid:\n                continue\n            others = grid[nb]\n            for i in members:\n                pi = pts[i]\n                for j in others:\n                    if nb == key and j <= i:\n                        continue\n                    pj = pts[j]\n                    d = math.sqrt(sum((a - b) * (a - b) for a, b in zip(pi, pj))) / (w[i] + w[j])\n                    if d < s:\n                        s = d\n    if s <= EPS:\n        fail(f\"pack({n}) has coincident centres (scale={s})\", \"wrong_answer\")\n    return w[n - 1] * s   # the largest object's radius (equal case: the common radius)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"pack.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import pack as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import pack.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"pack\"):\n        fail(\"pack.py must define pack(n, time_budget, seed)\", \"compile_error\")\n\n    ns = sorted(set(NS))\n    for n in ns:\n        if n not in RECORDS:\n            fail(f\"no Packomania record for n={n}\", \"error\")\n    seed_int = random.Random(f\"crc_600|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    t_all = time.perf_counter()\n    for n in ns:\n        t0 = time.perf_counter()\n        try:\n            centres = cand.pack(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"pack({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"pack({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        v = value_of(centres, n)\n        ratio = v / RECORDS[n]\n        per_n[n] = {\"value\": round(v, 12), \"record\": RECORDS[n], \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if v > RECORDS[n] + 1e-9:\n            beaten.append(n)\n    metric = sum(x[\"ratio\"] for x in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"ns\": ns, \"per_n\": per_n, \"records_beaten\": beaten,\n                      \"total_seconds\": round(time.perf_counter() - t_all, 1)}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"pack.py":"\"\"\"Baseline: a lattice of candidate points inside the container, spacing found by bisection so\nthat at least n fit. Deliberately naive; scores well below the records. Beat it.\"\"\"\n\nimport itertools\nimport math\n\nDIM = 2\n\n\ndef _boundary(c):\n    return min(c[0], 1 - c[0], c[1], 0.6 - c[1])\n\n\ndef _weight(i):\n    return 1.0\n\n\ndef _lattice(n, r):\n    \"\"\"Cubic lattice points at spacing 2r whose distance to the boundary is at least r.\"\"\"\n    lo, hi = ((0.0,) * DIM, (1.0,) * DIM)\n    step = 2.0 * r\n    axes = []\n    for d in range(DIM):\n        k = int((hi[d] - lo[d]) / step) + 1\n        axes.append([lo[d] + r + i * step for i in range(k)])\n    pts = [p for p in itertools.product(*axes) if _boundary(p) >= r]\n    return pts\n\n\ndef pack(n, time_budget, seed):\n    # treat every object as the largest one when choosing the lattice spacing\n    wmax = max(_weight(i + 1) for i in range(n))\n    # find a feasible spacing by halving, then bisect between it and the last infeasible one\n    a = 1.0\n    while len(_lattice(n, a * wmax)) < n and a > 1e-9:\n        a /= 2\n    b = 2 * a\n    for _ in range(40):\n        m = (a + b) / 2\n        if len(_lattice(n, m * wmax)) >= n:\n            a = m\n        else:\n            b = m\n    pts = _lattice(n, a * wmax)\n    pts.sort(key=lambda p: -_boundary(p))   # keep the most interior points\n    return [tuple(p) for p in pts[:n]]\n"}}