{"id":"circle-packing-rectangle-800","name":"Equal circles in a 1 × 0.8 rectangle","family":"combinatorics","description":"Place n circles in the rectangle [0, 1] × [0, 0.8] 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.8 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.8] (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_800`, 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 420) 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-800. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/crc_800/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.8]. Source: Packomania (E. Specht),\n# https://packomania.com/crc_800/crc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.400000000000000000000000000000, 2: 0.267544467966324133600221291114, 3: 0.223833696070628178173747954583, 4: 0.208578643762690495119831127579, 5: 0.188357266740185233085547600489,\n    6: 0.172613694011068949675426115515, 7: 0.155983960168048643595298614200, 8: 0.151662612389395853535683841774, 9: 0.144331195321985151697250280456, 10: 0.134224258574381790065222795652,\n    11: 0.133347460724735977412358558869, 12: 0.126322452478319825311877594386, 13: 0.119072443431197967377035895532, 14: 0.115156251600485524394653801874, 15: 0.112617236481240399971284622636,\n    16: 0.111129887168889730288663097818, 17: 0.106170692314551135413282932008, 18: 0.102981868809774241274631325689, 19: 0.101542459539147280449314249484, 20: 0.100000000000000000000000000000,\n    21: 0.095500509827938734152534464858, 22: 0.093609530103256944275449496239, 23: 0.092417255226161923847724098059, 24: 0.090425531914893617021276595745, 25: 0.089919399267489652200258118461,\n    26: 0.087062640429280983805211727293, 27: 0.085322779317815833632827537474, 28: 0.084340088756575576984319988601, 29: 0.083398168183174634737965093958, 30: 0.080986667745386336578458896655,\n    31: 0.080214937307274927186321623011, 32: 0.080021775095394196752104916597, 33: 0.077957865600844411603253164885, 34: 0.076233568624217023440015742984, 35: 0.075856940904150392372391468868,\n    36: 0.075505534593545460651581324040, 37: 0.073568574016070527641664260205, 38: 0.072890905684027670903328698176, 39: 0.071969970506444457905924439148, 40: 0.071585465729344188896337168687,\n    41: 0.070165716059027627383043308627, 42: 0.069110251506051524732967296468, 43: 0.068192720630483868045748100180, 44: 0.067704183267549417852677702048, 45: 0.067054307873368633575764955974,\n    46: 0.066674416812048080185571801327, 47: 0.065589888669514147182363779599, 48: 0.065277552294993889335577521480, 49: 0.065078237692110609335543824476, 50: 0.064197067266620434474813002025,\n    51: 0.063350777978652333386702529866, 52: 0.062930698071933833900005509666, 53: 0.062670013122123255384678366458, 54: 0.062007341694591756722645255595, 55: 0.060865465652809370527816114909,\n    56: 0.060251757547649745566639287656, 57: 0.059607365793457050070870641312, 58: 0.059168171244214064726926683352, 59: 0.058749107103760024718972964133, 60: 0.058537287973749982127615445398,\n    61: 0.057876159181225037025340338168, 62: 0.057670909554008571696346797750, 63: 0.057325065828633922879914388191, 64: 0.057183306192520156714167615762, 65: 0.056929613282050999659491157953,\n    66: 0.056279684084868147915577768199, 67: 0.055800526792228472010922347178, 68: 0.055652909818278224269435994077, 69: 0.055555646379566914274390034963, 70: 0.054241213386980203204459544102,\n    71: 0.053841738003889231018002569093, 72: 0.053591198129264284035739014174, 73: 0.053086301783543024245574709691, 74: 0.052699597411196553954433754160, 75: 0.052365749298295452253889400723,\n    76: 0.052314721021861216967473472095, 77: 0.052171460843930845058510324566, 78: 0.051611169782250225818066420626, 79: 0.051265729976640373405183608807, 80: 0.051120944138678835638499148385,\n    81: 0.050997603160693280761027412856, 82: 0.050638400255208459687691205093, 83: 0.050506127621684673772686360735, 84: 0.050241723652679180606822256891, 85: 0.050064198790273211019305555533,\n    86: 0.050013999247632022259596864289, 87: 0.049137061066949403359751080795, 88: 0.048661947946253821208584506536, 89: 0.048383147704156215305412037093, 90: 0.048170334424546069622230987009,\n    91: 0.047791502446871553973610993892, 92: 0.047658199371930979687178123848, 93: 0.047494500917392956193445065967, 94: 0.047326151141032882602005497965, 95: 0.047201245140337711660831003112,\n    96: 0.047131905389808397317205105331, 97: 0.046465778713880410716871523930, 98: 0.046250823276994035771814734184, 99: 0.046141127793533851421622246592, 100: 0.046020039172959540684213038866,\n    101: 0.045738842021252803765655554646, 102: 0.045635212533860954892340102847, 103: 0.045510032736024620800419872092, 104: 0.045457958233436040732030093043, 105: 0.045454681838679038324818529680,\n    106: 0.044957742918623742735415143232, 107: 0.044242210462879179973380658410, 108: 0.044139805122014646223272946034, 109: 0.044081917164168436306425366468, 110: 0.044069520685278056908085645381,\n    111: 0.044032267581103002691045547771, 112: 0.043333593629283880991341683389, 113: 0.043100863588385861103708704752, 114: 0.042826108819098200996837070686, 115: 0.042629163053549346013953222938,\n    116: 0.042608626337325656800702557691, 117: 0.042403519198549880050340529148, 118: 0.042234329521309774149027574885, 119: 0.042093590218440867786102227112, 120: 0.042053258151036513656099006521,\n    121: 0.041928035226567055074104936007, 122: 0.041717178046133191103851754376, 123: 0.041658103776770641786228328925, 124: 0.041560535361535079408157027930, 125: 0.041494338549433757497637167098,\n    126: 0.041477091827687327486996327525, 127: 0.041470837350693090281419460028, 128: 0.040772418647263162243643191953, 129: 0.040604698315454488257823688300, 130: 0.040404836095477188064314160316,\n    131: 0.040283518045120274664476021254, 132: 0.040252186562917299766975108601, 133: 0.040054517074150308700204913505, 134: 0.040004280651692916801353660189, 135: 0.039623004562204550901171957807,\n    136: 0.039361073481863738287944388902, 137: 0.039330789040860073359687373261, 138: 0.039318454782297415075332384910, 139: 0.039040925852364094780192810642, 140: 0.038896233580654893352170936135,\n    141: 0.038722749966316070653060829907, 142: 0.038669902703102882089707094307, 143: 0.038636452608942184642366782069, 144: 0.038504503350930265589910568290, 145: 0.038311596794096885822573853657,\n    146: 0.038233225969577254503124950189, 147: 0.038205212469119990557153037075, 148: 0.038157288473604982842458921029, 149: 0.038129541133170228197315939055, 150: 0.038114344904569438684745003442,\n    151: 0.037769246847516997990437783397, 152: 0.037628929625831103447301616988, 153: 0.037410413009030624095049633872, 154: 0.037305396007364292797165816710, 155: 0.037221710355953291915875477902,\n    156: 0.037185509620662748195977881614, 157: 0.036815687698699073154728442365, 158: 0.036769788135288669844338830979, 159: 0.036538645310731765772179014824, 160: 0.036408417167807344768737943173,\n    161: 0.036365138255698227036608040304, 162: 0.036347561303529154525191286676, 163: 0.036133861854572842967534451563, 164: 0.036046056542177428703875185425, 165: 0.035992104641561697847492387890,\n    166: 0.035958579397542719661398955706, 167: 0.035944606045124990413045402260, 168: 0.035900347968219895799651532134, 169: 0.035657696093755672077015432269, 170: 0.035503906948750796657048865962,\n    171: 0.035422160123188903299643948021, 172: 0.035389417048260662483431829021, 173: 0.035312130277621140840392460641, 174: 0.035287377808868588610215986129, 175: 0.035282999759448591401495101511,\n    176: 0.035261173308729576181523615833, 177: 0.034966145715509192996016047970, 178: 0.034857160883260231799989308212, 179: 0.034728994582312797587988841688, 180: 0.034665024581971799077779007972,\n    181: 0.034592811265294631379341127944, 182: 0.034561678615000248321117480376, 183: 0.034209431925663544684324808054, 184: 0.034092531367049947118522006774, 185: 0.034086648851788482706364290660,\n    186: 0.033996022301361596942900640903, 187: 0.033958684010216784282613243385, 188: 0.033798574421844314917018421392, 189: 0.033798574421844314917018421392, 190: 0.033594474433158624372445120936,\n    191: 0.033560574848948713441126403448, 192: 0.033467604342388333442622552734, 193: 0.033429604179389387094923898939, 194: 0.033387569444461777921186456506, 195: 0.033358755559633843016617738708,\n    196: 0.033343058557456723450881725939, 197: 0.033127574986995419413996714059, 198: 0.032935920401216303611093144058, 199: 0.032901050069105382304201883118, 200: 0.032860370967364766184489011699,\n    201: 0.032843499480092859384500228384, 202: 0.032835684067677104295734345291, 203: 0.032806837014728598665907610291, 204: 0.032645673531096339848407777080, 205: 0.032552476148505615225274200333,\n    206: 0.032490706716386073950294276882, 207: 0.032416816444998895279145374189, 208: 0.032367873854827791001487308484, 209: 0.032322051258146275468348778306, 210: 0.032294356419874184300307351015,\n    211: 0.031947331185854850657181489140, 212: 0.031895601267320373409815884567, 213: 0.031875156516662719823037999583, 214: 0.031867182896033067337646976094, 215: 0.031867098789556438864213362544,\n    216: 0.031852058153983080295271049471, 217: 0.031498184144690623230095968817, 218: 0.031439945464370239248908888768, 219: 0.031291828211934887385613899766, 220: 0.031266481759747208093828643284,\n    221: 0.031175496196931956139154408646, 222: 0.031115879015536821128160343207, 223: 0.031093869731108328962404909637, 224: 0.031084592203018774423789993918, 225: 0.030934645041041567131913697267,\n    226: 0.030884832775880643966112293890, 227: 0.030847910477960896316141010569, 228: 0.030826111404308385573536356047, 229: 0.030764284649778132461596909013, 230: 0.030727042725439267177165626915,\n    231: 0.030710177509329397996974757124, 232: 0.030708338179137274276788619121, 233: 0.030671518430252557897834347824, 234: 0.030549340677304257804913627313, 235: 0.030485660061233107932514137213,\n    236: 0.030410813100418980725457093911, 237: 0.030389388601581105357329993432, 238: 0.030364355682275830971544107144, 239: 0.030331715268164589601180229626, 240: 0.030318842132217197123643715155,\n    241: 0.029913929545005962520274079892, 242: 0.029860743706544576760970619842, 243: 0.029825829793355073028412642414, 244: 0.029785896075546332105106196789, 245: 0.029741399916632819316236544838,\n    246: 0.029711783135304936089574200783, 247: 0.029688057698606756368356633351, 248: 0.029652663846259747625866323014, 249: 0.029477290781052645753804034807, 250: 0.029362241654946991483879987955,\n    251: 0.029326103639881635928728240122, 252: 0.029266222131938283397352977675, 253: 0.029212805651967314841990676582, 254: 0.029193249552934005802112511058, 255: 0.029188765974011792539136345577,\n    256: 0.029074821794781369804899207185, 257: 0.029036701890422310772098565187, 258: 0.029003112258528566110258637597, 259: 0.028921134697222417127502622609, 260: 0.028913981920595788234709213940,\n    261: 0.028855441946431942228590519378, 262: 0.028843702582290154768063505341, 263: 0.028842093796677487992045084521, 264: 0.028798438918180130438192135445, 265: 0.028705931497536672164241919131,\n    266: 0.028677852667970647443541784685, 267: 0.028660224907114313435145702388, 268: 0.028617901369637940103229663759, 269: 0.028596403654611543332219616335, 270: 0.028587978748602439114067031174,\n    271: 0.028574822174385153276854926133, 272: 0.028573090771735272324391762048, 273: 0.028312507632754132659491832323, 274: 0.028210176946752356907932846776, 275: 0.028122779491927978417776555173,\n    276: 0.028052315954321463521233538999, 277: 0.028004757553154768826910930909, 278: 0.027955781099355888809921155468, 279: 0.027928630154594524635364298415, 280: 0.027898250805148835786320750349,\n    281: 0.027834094719982368747859974727, 282: 0.027694965865344580099689310694, 283: 0.027648971904555920285254894789, 284: 0.027648966998324006562859705363, 285: 0.027548349948542578476415216083,\n    286: 0.027534463318271002852004235391, 287: 0.027445229170454912782373201897, 288: 0.027420009173205848340990343910, 289: 0.027402957045610760360804488069, 290: 0.027395288765424986388183194997,\n    291: 0.027393114649431895233280458568, 292: 0.027389932112204019315974201794, 293: 0.027371720593893290216531365184, 294: 0.027366585808025824903514268125, 295: 0.027200724859412082555107105433,\n    296: 0.027191946143109374734621530333, 297: 0.027190762998291987240635814300, 298: 0.027140435876967612003213228072, 299: 0.027047899137704676016700656621, 300: 0.027028620625486151932012062137,\n    301: 0.026983773571805253256427716610, 302: 0.026968004125984256791687854571, 303: 0.026959408141133162739597324451, 304: 0.026954790215774993574444371425, 305: 0.026951916124068547171458291137,\n    306: 0.026949833325738645382745208191, 307: 0.026747113627037078007753495598, 308: 0.026652247962902213425979820160, 309: 0.026621401881189168310026711740, 310: 0.026572922821775014129012528244,\n    311: 0.026521088530336774560299360958, 312: 0.026465894313054987195697588039, 313: 0.026427389291553521847933763638, 314: 0.026426835591463938900052989532, 315: 0.026426835591463938900052989532,\n    316: 0.026315793045451815698185190533, 317: 0.026254181683535617755558095863, 318: 0.026229937117265293552936490668, 319: 0.026218346598160801502864035605, 320: 0.026103966691100260184367465212,\n    321: 0.026088972270526150346516738842, 322: 0.026069551735647441837230702474, 323: 0.026022867708217859798512041474, 324: 0.025978266880277257748995024339, 325: 0.025933154226097639036384863056,\n    326: 0.025906580145529061700752565928, 327: 0.025878156767388208170948306995, 328: 0.025857628123087029887205921968, 329: 0.025840307777657113124620329688, 330: 0.025830778061764582460971449308,\n    331: 0.025722538045509997956351508645, 332: 0.025721790771915031648677968397, 333: 0.025658863198515251275443763278, 334: 0.025598009079072475911792747347, 335: 0.025574584424040945425602623053,\n    336: 0.025555377487651609062482286891, 337: 0.025533047237699746360724811738, 338: 0.025530236313569610349391048700, 339: 0.025508358818866925928984373788, 340: 0.025497754141553846966030270355,\n    341: 0.025496900829296905380350446702, 342: 0.025490940304954718900522402783, 343: 0.025287740233667987504655463283, 344: 0.025266577458661793654518353487, 345: 0.025230323236626272671445333805,\n    346: 0.025194650445464694683103622292, 347: 0.025137691040002553542978632374, 348: 0.025104063517577058209810477461, 349: 0.025080377659040966655109306147, 350: 0.025061625675758979711446197227,\n    351: 0.025045751604207096606690328455, 352: 0.025004953761503547774941578073, 353: 0.024957060312864803794213430170, 354: 0.024955679678082896527640650062, 355: 0.024955669565855307185669594619,\n    356: 0.024953443071286955920099595130, 357: 0.024951037439775476092505275361, 358: 0.024750070461744888240143519367, 359: 0.024634713192037511999714728166, 360: 0.024630259554278278930423208243,\n    361: 0.024589269734074286963535091623, 362: 0.024575342320276234007986663167, 363: 0.024543792715300309390783781552, 364: 0.024499454933968850982864007027, 365: 0.024481336007844846719187057914,\n    366: 0.024431377186122072967406223658, 367: 0.024418791989480464928018431385, 368: 0.024405985919593688223374153726, 369: 0.024404393256922105273734665216, 370: 0.024386646356920839103945811718,\n    371: 0.024337406630271112784861993231, 372: 0.024275460384233554861540316749, 373: 0.024260927219296362496240764208, 374: 0.024232692030376433501532050403, 375: 0.024210217975473170331077951313,\n    376: 0.024207112010290863386589693971, 377: 0.024195623640882113905956083791, 378: 0.024192744196866064129572559685, 379: 0.024192204097858655878176323468, 380: 0.024182731204195553928763984866,\n    381: 0.024071515792360218468854669987, 382: 0.024013317381431524695125874979, 383: 0.023995843461698667148159633207, 384: 0.023988598996017552480422318754, 385: 0.023933289720763227947965393595,\n    386: 0.023897543756463322319921333035, 387: 0.023871291302878894427772175886, 388: 0.023848376539816648640120148446, 389: 0.023848376539816648640120148446, 390: 0.023848376539816648640120148446,\n    391: 0.023749767409904687477827387630, 392: 0.023613038690450029927681408090, 393: 0.023602738785749041946853624368, 394: 0.023596075694255367167226912626, 395: 0.023586305314978049103719342292,\n    396: 0.023567897657812978479593110717, 397: 0.023543028744323624697409754030, 398: 0.023442510423282873529346494946, 399: 0.023438599473962574068301176688, 400: 0.023375155615757946303843449761,\n    401: 0.023320648325443582458694133107, 402: 0.023311905356434582621461306461, 403: 0.023299246322880320677237307726, 404: 0.023277504668425958538701464377, 405: 0.023245345069492052087467509870,\n    406: 0.023232681281922364745681321272, 407: 0.023219373669097719015319357923, 408: 0.023200767068844031107365551688, 409: 0.023166295061026001515430360106, 410: 0.023131426654880218485992371445,\n    411: 0.023104154286463190140769621116, 412: 0.023084996066391255201351904084, 413: 0.023077306638227564048646632416, 414: 0.023058206565791930013990494366, 415: 0.023039084103939653067099464458,\n    416: 0.023024148941025266059732083639, 417: 0.023017666903705030055789713905, 418: 0.023015962110374617980404777391, 419: 0.023015916469319962433876816207, 420: 0.023002082502461642363309917591,\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.8 - 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_800|{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.8 - 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"}}