{"id":"circle-packing-rectangle-700","name":"Equal circles in a 1 × 0.7 rectangle","family":"combinatorics","description":"Place n circles in the rectangle [0, 1] × [0, 0.7] 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.7 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.7] (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_700`, 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 437) 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-700. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/crc_700/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.7]. Source: Packomania (E. Specht),\n# https://packomania.com/crc_700/crc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.350000000000000000000000000000, 2: 0.258392021690038395743267170844, 3: 0.205892565390258373770817432927, 4: 0.190231221598761233193745028355, 5: 0.175717864185549522550153430972,\n    6: 0.167158248695502731670384586987, 7: 0.146332224376070850817050427221, 8: 0.139271215442889792000684604206, 9: 0.131686637214672965358289152472, 10: 0.127324919471876015312873323879,\n    11: 0.125147988256670698128060981604, 12: 0.118556819856559100849105133863, 13: 0.113363312053730327942160413968, 14: 0.108161900810807857786497088150, 15: 0.104896986540439113264399052252,\n    16: 0.100846457631309104197582078435, 17: 0.098636659915971426480019342099, 18: 0.097913275434164037349274546765, 19: 0.095098067879851095997843276275, 20: 0.092857142857142857142857142857,\n    21: 0.089253147700753232893098243002, 22: 0.088021174862587805588184691571, 23: 0.087262813098028571559713327287, 24: 0.084200604058685361468391373641, 25: 0.082757390797390305651343328240,\n    26: 0.080919062810375005253994914123, 27: 0.080024385703091483748519100802, 28: 0.079604774283339131262714745062, 29: 0.077936804406052390081579370517, 30: 0.077272727272727272727272727273,\n    31: 0.074848562871263167211984873834, 32: 0.074023210305284956740704566116, 33: 0.072729408259063972041912369870, 34: 0.071756184271447685637716992903, 35: 0.070334536151109295087018593032,\n    36: 0.070041043140013981819522063390, 37: 0.069602842206588458016803833737, 38: 0.067738478320275643202916882003, 39: 0.067133324617144897372505466462, 40: 0.066334648857052592918875412100,\n    41: 0.066031090064732256684994375895, 42: 0.065904688508696891142503952863, 43: 0.064260797556073890506673162019, 44: 0.063668014876580696071888410239, 45: 0.063216340383991832998506773965,\n    46: 0.062625942915089805909080484752, 47: 0.061433993094167758077339192797, 48: 0.060545277328947515494466862204, 49: 0.059885888727617844595021122675, 50: 0.059391831265027711718710105853,\n    51: 0.058844562023254324380899729144, 52: 0.058432840218023793774310242289, 53: 0.058051238682323110954158195238, 54: 0.057490648556709649878292975831, 55: 0.057246621739955734089123546245,\n    56: 0.057079044963796210194047663863, 57: 0.056574708487379293427803106219, 58: 0.056073726692250897353553684481, 59: 0.055737024349492942255091535159, 60: 0.055614095090467682713072238960,\n    61: 0.054524912520642854945880597708, 62: 0.053792657419078793503436786729, 63: 0.053333972215302442504605623570, 64: 0.052916789201406106279826141222, 65: 0.052477091876488782448099789269,\n    66: 0.052312687566895883272234365838, 67: 0.051763086763323929617498142711, 68: 0.051381774483884842761931025943, 69: 0.051070764921551307901946410908, 70: 0.050726199215756024399565471827,\n    71: 0.050589655296940238398790261317, 72: 0.050353753263639442842334740131, 73: 0.050007651343488671782457857521, 74: 0.049784498252947302710255735743, 75: 0.049700465673074189985757373681,\n    76: 0.049666378877808812673420637250, 77: 0.048974373533981839717857197960, 78: 0.048446874110363620837894029312, 79: 0.048149737844292085990957543317, 80: 0.047917341844487866755766392500,\n    81: 0.047361148031253469630782707348, 82: 0.047106955181550783773475602849, 83: 0.046926542843980016372992817587, 84: 0.046821660771319938391478951181, 85: 0.046228763708287895283345802490,\n    86: 0.045906287015557137508610833570, 87: 0.045690830700752213605133206804, 88: 0.045421536735251749168288160429, 89: 0.045284248342325280158819939359, 90: 0.045063618475774893497000040657,\n    91: 0.044827999845571342380733485239, 92: 0.044694261550766240052515847562, 93: 0.044582386076288906664750984499, 94: 0.044541654888297572167936301153, 95: 0.044471547066723449707905736020,\n    96: 0.044172292072017878966619659190, 97: 0.043822862131955106163245636846, 98: 0.043672216580868364443683718263, 99: 0.043567405950144131719933107167, 100: 0.042967348623505254471836570977,\n    101: 0.042742738777919416281004367869, 102: 0.042436365898685296402132709476, 103: 0.042199237268620921335294431688, 104: 0.042169849119418017960878665350, 105: 0.041798275534226474010642437486,\n    106: 0.041529313910682627607061188446, 107: 0.041364669953437850897298662365, 108: 0.041196411726600244444492150009, 109: 0.041012318528019390539436847718, 110: 0.040947907249312236227783657150,\n    111: 0.040906106126673551107392170901, 112: 0.040888897391999618748627921058, 113: 0.040441912936944149392680566248, 114: 0.040426669910353026609636172381, 115: 0.040284969930811727765555521282,\n    116: 0.040045076786409452710128546772, 117: 0.039964438557230056806858624622, 118: 0.039891003952282283345203008251, 119: 0.039859129485117269265294164158, 120: 0.039847829197763949498991351103,\n    121: 0.039286482743469243760163776373, 122: 0.039127305347762422272966200125, 123: 0.038919064374967975673584884793, 124: 0.038725198679952218947591542419, 125: 0.038637048724904784623213337153,\n    126: 0.038528271489763310787874822984, 127: 0.038350058854159177920148387632, 128: 0.038302570481042099629017838923, 129: 0.037874383606925062659619967876, 130: 0.037686828043399282983284448792,\n    131: 0.037542552000919332387449117158, 132: 0.037394638467319262866769724869, 133: 0.037218331466544864304962072641, 134: 0.037126896601780637809023846371, 135: 0.037058276433791298394105125726,\n    136: 0.036965681182585385750308235271, 137: 0.036884352548964042679140134613, 138: 0.036825022506139029059837700496, 139: 0.036659815135021273263497354793, 140: 0.036561844585918064633178120126,\n    141: 0.036495586534724440533744248782, 142: 0.036475266243951032518363212966, 143: 0.036432092554263451988750954019, 144: 0.036259508791085745557716102164, 145: 0.036158813501239574648465590655,\n    146: 0.035944695149952502399227211818, 147: 0.035848020819740986871600782383, 148: 0.035778943860868034836384683032, 149: 0.035746800529412666069304921000, 150: 0.035379758546600275491844034634,\n    151: 0.035125399319497946852350837768, 152: 0.035032679447906249898836800116, 153: 0.035008059727787206043318457393, 154: 0.034810530433773789228015396589, 155: 0.034620302170821845819774808272,\n    156: 0.034458090040123598670162494283, 157: 0.034383683847963477299051231361, 158: 0.034278991277997032083177493813, 159: 0.034214346162395224820055082986, 160: 0.034110087521970959553787888958,\n    161: 0.033978700794880358138276063902, 162: 0.033926742206370845942860304777, 163: 0.033827232055424297573680483089, 164: 0.033760957332570278407461993767, 165: 0.033697316186754197041362244650,\n    166: 0.033667325633897840617754564861, 167: 0.033605330944917836056516627001, 168: 0.033572013946993447206892981581, 169: 0.033424655209037930171990125366, 170: 0.033381979966146668207863484315,\n    171: 0.033317130252161349602580365369, 172: 0.033289711554239429634193405191, 173: 0.033274791005750542686793059329, 174: 0.033270462881623420608347819623, 175: 0.032960554151004654256492456637,\n    176: 0.032763841638202684860963414267, 177: 0.032644061668012050649845328838, 178: 0.032511955628503771519992668971, 179: 0.032423517658237893676376477853, 180: 0.032371607381062897132755567209,\n    181: 0.032216741337194731348039125926, 182: 0.032040705415279004177978690937, 183: 0.031925708297746697867995855975, 184: 0.031844174407583025002282682989, 185: 0.031819504997561122003915939222,\n    186: 0.031807170160261533200670605087, 187: 0.031645212471856445708291815499, 188: 0.031629906495741722802884706480, 189: 0.031617616782494775727046219775, 190: 0.031418078731439135724368442367,\n    191: 0.031343623468239481991598852902, 192: 0.031281991316498124701425787078, 193: 0.031269142139481334510909090001, 194: 0.031159999127201480969881276135, 195: 0.031133308759598885033330078871,\n    196: 0.031008300696750470197110947147, 197: 0.030983113515006265401189003996, 198: 0.030932007116863156978415059810, 199: 0.030898200966284484207291473484, 200: 0.030889733748551800177632633537,\n    201: 0.030866239361593085472628781259, 202: 0.030854372076601718241705688335, 203: 0.030718260947590295677534969246, 204: 0.030619545669136592468371807633, 205: 0.030515260186957251771373125063,\n    206: 0.030422571802385026966626484858, 207: 0.030371665865786286538931654968, 208: 0.030342145940068221201914529119, 209: 0.030083154544520346627000581893, 210: 0.029985031735515407941869762094,\n    211: 0.029882212828119280022052433050, 212: 0.029806434831821343592673829196, 213: 0.029738999680865345466623848517, 214: 0.029674844171813738402908909898, 215: 0.029665179011083418336720003826,\n    216: 0.029483357055965719991747346196, 217: 0.029399637952356164682253122944, 218: 0.029328798743165601768268158873, 219: 0.029262205268033870183459826893, 220: 0.029239428477735430870451888754,\n    221: 0.029212730457715600518389693994, 222: 0.029212078949909187185103483908, 223: 0.029072660016491866729885814036, 224: 0.029034509428316777385416584865, 225: 0.028988576342011552988088119640,\n    226: 0.028944162331089752930550786360, 227: 0.028870136300345710412711452736, 228: 0.028846552690553455014845888571, 229: 0.028840086180779656437854965503, 230: 0.028801271943674297841307923139,\n    231: 0.028776832805537896756253745812, 232: 0.028673438041834041915053479904, 233: 0.028645178831316469447076343900, 234: 0.028595884410067751646076302036, 235: 0.028565732837173503724770829433,\n    236: 0.028560860268414765329156638340, 237: 0.028557716423546672477079822171, 238: 0.028556772953917451872042971351, 239: 0.028261091571216945035019257877, 240: 0.028190799001182559707818031468,\n    241: 0.028109017078741013086409163418, 242: 0.028015874675834566828424145925, 243: 0.027942060176863751653401447832, 244: 0.027916022465499722320268881936, 245: 0.027885780606082855055689723856,\n    246: 0.027826457424809671714439110798, 247: 0.027627821969026663894988852878, 248: 0.027569033588096554795132148310, 249: 0.027503274292393338252001114625, 250: 0.027470443512538894428588228615,\n    251: 0.027459786300045151541910586784, 252: 0.027432962414632842742252651642, 253: 0.027362010988476033318053668779, 254: 0.027257162928506415663639137644, 255: 0.027221018655478180942119482921,\n    256: 0.027131438080532030800004003860, 257: 0.027111770063023043147549090113, 258: 0.027086427181355894332319524193, 259: 0.027070805644898719778016148136, 260: 0.027063141207505655062634411475,\n    261: 0.027022625695940291779283719929, 262: 0.026971417513661541336110958554, 263: 0.026965567635797728125023034986, 264: 0.026889392949336265400240850359, 265: 0.026856817278125635983592800047,\n    266: 0.026809862235988009044869335638, 267: 0.026785018743636236226355272626, 268: 0.026780647818529112079306514362, 269: 0.026766316032631842849847713824, 270: 0.026757815357156105041211736180,\n    271: 0.026670399637860406816827665510, 272: 0.026611598615204408491238906763, 273: 0.026550929743523651196092750836, 274: 0.026465831105105946231696448809, 275: 0.026405790198910335697576169111,\n    276: 0.026373532908827678596349613101, 277: 0.026350960483270269579811382573, 278: 0.026341208893262979652439293919, 279: 0.026140777209482647816282939505, 280: 0.026036675387823430833573508672,\n    281: 0.025990408622237375993721963094, 282: 0.025934059511337326204259296329, 283: 0.025882290615011982887292085051, 284: 0.025859603937490617612825194076, 285: 0.025820457710821821476426547980,\n    286: 0.025746579536361108583892923038, 287: 0.025672941520360475686847974721, 288: 0.025671823493234621949251789093, 289: 0.025607084892153368342566973960, 290: 0.025576748031841497029253119597,\n    291: 0.025533446519243149337257656583, 292: 0.025511021209684828718805291137, 293: 0.025506062271840072768117720898, 294: 0.025433967184201990678261909940, 295: 0.025383463717889775212755253456,\n    296: 0.025374385974072111747285919546, 297: 0.025337676739791747600003977021, 298: 0.025304544132583077148733316528, 299: 0.025249989843258255490793034400, 300: 0.025230936528290507526890918540,\n    301: 0.025225402945813599535726987521, 302: 0.025225232885989289930131008788, 303: 0.025186854961595985225180496362, 304: 0.025180330607564362651343222834, 305: 0.025085584383294077341672624093,\n    306: 0.025065750889214232977706212887, 307: 0.025030664648400564308261727690, 308: 0.025020480591271075251814122990, 309: 0.025009592782727846807908299189, 310: 0.025000118092511828942649878031,\n    311: 0.025000118092511828942649878031, 312: 0.025000118092511828942649878031, 313: 0.024835197893705631182021457816, 314: 0.024709312520450022739819050351, 315: 0.024654723094324338061973694548,\n    316: 0.024609832600810932915224842718, 317: 0.024551334189886278183393711321, 318: 0.024523853475853010505161126123, 319: 0.024497468496362584697151646386, 320: 0.024451813301075792629333497396,\n    321: 0.024325622010223022611787834421, 322: 0.024290253519281921936939618379, 323: 0.024233083758085976229144960436, 324: 0.024202560065421772323949376446, 325: 0.024166123069577285927218675426,\n    326: 0.024149304630295529615893474700, 327: 0.024138065520629440702546149448, 328: 0.024133787915369222796671788408, 329: 0.024038319878633964296189349988, 330: 0.024012829716813352981041353937,\n    331: 0.024001960176109461739042139625, 332: 0.023982382278513584575501119968, 333: 0.023978895272694527991521186556, 334: 0.023976070860800200029782719409, 335: 0.023974631709267674259634570598,\n    336: 0.023962359873140659995666055511, 337: 0.023844924266386995495058727568, 338: 0.023808208581619536230919138724, 339: 0.023785909384304898211246549766, 340: 0.023781994142671214607833421901,\n    341: 0.023717909889284751816076319841, 342: 0.023677381273894284292880212638, 343: 0.023668784562508404000144620316, 344: 0.023649449168948689160548290579, 345: 0.023644204643894152456048721616,\n    346: 0.023638241609579585311297096498, 347: 0.023634338212668059164282292883, 348: 0.023625447345592903435571749019, 349: 0.023621591172422675888258728595, 350: 0.023470511529669562202069590188,\n    351: 0.023436328093724970764003343767, 352: 0.023420082202713330611177076439, 353: 0.023373728664177613049121185897, 354: 0.023336629330658799271231022397, 355: 0.023308684020541875472291449299,\n    356: 0.023291928286393933536967310679, 357: 0.023279000699912890278682964543, 358: 0.023156626393226301161916476978, 359: 0.023078899867494748405653375531, 360: 0.023078888404996200187993000107,\n    361: 0.023078710080622639973623769858, 362: 0.023065112748270831154721259735, 363: 0.023050176900742576256967081222, 364: 0.022928303185165924118968541968, 365: 0.022916514490583086467920315139,\n    366: 0.022896524634503335895574445483, 367: 0.022780601122152370504659895908, 368: 0.022738614896548940637530613647, 369: 0.022736795760008753135895737941, 370: 0.022698489079468187873697177580,\n    371: 0.022664578348515222597425867978, 372: 0.022659857568601391825628387801, 373: 0.022646912489741795661452021726, 374: 0.022636229213064692303082973491, 375: 0.022629688520526817506843113387,\n    376: 0.022565664523671938285815923662, 377: 0.022541468199915560058504828206, 378: 0.022529892709989323399998455554, 379: 0.022490863284948034279736335357, 380: 0.022477385189315918971604957092,\n    381: 0.022444635197571134566532951885, 382: 0.022425460879602404526399912175, 383: 0.022417629969157757106164870344, 384: 0.022415915304074329999081716168, 385: 0.022405618826067047973139253650,\n    386: 0.022387690233130496222859652860, 387: 0.022382982114197555619841001823, 388: 0.022309954169559146542689814034, 389: 0.022287534410154598132169998561, 390: 0.022256839566856413886855711117,\n    391: 0.022254755643108566197068935618, 392: 0.022243987272294359801460576518, 393: 0.022243834742772965701797817097, 394: 0.022234713903364975509413541468, 395: 0.022227010524294292443884629539,\n    396: 0.022224820450688262909166183136, 397: 0.022050168654090634072705368773, 398: 0.021987828834989929408614308710, 399: 0.021964481426075379747719034230, 400: 0.021933319714099063129790051849,\n    401: 0.021888084211858707870673848487, 402: 0.021836340064251285358244249227, 403: 0.021811109086428706270625581658, 404: 0.021793869612576501436229101973, 405: 0.021769834235195380018014420043,\n    406: 0.021754387226292455348588536777, 407: 0.021713851777567236055874943598, 408: 0.021639434169714228251899616294, 409: 0.021612675227558085671702790896, 410: 0.021579777953391747942506696045,\n    411: 0.021516223073151526773268893588, 412: 0.021489895834497482408345310705, 413: 0.021468508894633577352886698028, 414: 0.021468235524846591371421636042, 415: 0.021455213556040363560052394100,\n    416: 0.021424571098572988306917036953, 417: 0.021409775909464243861879223297, 418: 0.021384194087312495721924082476, 419: 0.021363349107804896245247360825, 420: 0.021347084766781176812433908193,\n    421: 0.021338099914628065128558515021, 422: 0.021329295871177340118233467011, 423: 0.021319302329004406793595676464, 424: 0.021309657165625517578882045365, 425: 0.021276042541124347957403537353,\n    426: 0.021261229008882521614911795395, 427: 0.021243080304677384049374930506, 428: 0.021221184358451038964220265486, 429: 0.021209402920442373202881020456, 430: 0.021200783252711678352811766209,\n    431: 0.021183838670058295663819910390, 432: 0.021162400852159088515975663451, 433: 0.021156769462640853172050747495, 434: 0.021154550142252941432823247146, 435: 0.021151709002469172968128228953,\n    436: 0.021146168351962472767012467129, 437: 0.021143440048726568753888364984,\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.7 - 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_700|{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.7 - 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"}}