{"abstract":"No swaps happen so no pairs ever begin or end.","category":"Collision detection broadphase","checks":8,"contract":"solve(prev, curr): incremental sweep-and-prune on x. Endpoints [x, 0=min/1=max, id] of prev are sorted, refreshed with curr coordinates and insertion-sorted by (x, kind). Each swap where a min passes left over a max begins a pair (if y overlaps in curr); a max passing left over a min ends a pair. Return [sorted begin pairs, sorted end pairs, swap count], pairs as [min,max].","contract_signature":"prev, curr","evaluation_group":"w2-collision_detection_broadphase-incremental-sap-swaps","failed_approach":"Seeding from prev but sorting by id breaks the sweep order.","family":"w2-collision_detection_broadphase-incremental-sap-swaps-seed-ordering","id":"FA-87806","implementations":{"attempt":{"sha256":"b4d1ff320c09f2470ea842e3c334628b797cf10725032d8e37cf0e8d5fa42fe2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prev, curr):\n    old = {b[0]: b for b in prev}\n    new = {b[0]: b for b in curr}\n    E = []\n    for i, b in old.items():\n        E.append([b[1], 0, i])\n        E.append([b[3], 1, i])\n    E.sort(key=lambda e: e[2])\n    for e in E:\n        b = new[e[2]]\n        e[0] = b[1] if e[1] == 0 else b[3]\n    def yover(a, c):\n        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]\n    begins, ends = set(), set()\n    swaps = 0\n    for i in range(1, len(E)):\n        j = i\n        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):\n            e, f = E[j], E[j - 1]\n            E[j - 1], E[j] = e, f\n            swaps += 1\n            p = (min(e[2], f[2]), max(e[2], f[2]))\n            if e[1] == 0 and f[1] == 1:\n                if yover(e[2], f[2]):\n                    begins.add(p)\n            elif e[1] == 1 and f[1] == 0:\n                ends.add(p)\n            j -= 1\n    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[28, 5.0, 2.0, 7.0, 2.0], [8, -1.0, -1.0, 0.0, 0.0]], [[28, 7.0, 1.0, 9.0, 1.0], [8, -4.0, -2.0, -3.0, -1.0]]], [[], [], 0]], [[[[10, 1.0, -5.0, 3.0, -4.0], [15, -2.0, 4.0, -2.0, 7.0], [19, -3.0, -1.0, 0.0, 1.0], [14, 1.0, 1.0, 4.0, 3.0], [22, 3.0, -3.0, 3.0, -1.0]], [[10, -2.0, -5.0, 0.0, -4.0], [15, 0.0, 4.0, 0.0, 7.0], [19, 1.0, 0.0, 4.0, 2.0], [14, 1.0, 1.0, 4.0, 3.0], [22, 2.0, -4.0, 2.0, -2.0]]], [[[14, 19]], [[10, 14], [10, 19], [10, 22], [15, 19]], 13]], [[[[15, -4.0, 5.0, -4.0, 8.0], [26, -1.0, 3.0, -1.0, 4.0], [31, 0.0, -2.0, 1.0, 0.0], [33, 3.0, -3.0, 6.0, -2.0]], [[15, -7.0, 5.0, -7.0, 8.0], [26, -1.0, 2.0, -1.0, 3.0], [31, 0.0, -2.0, 1.0, 0.0], [33, 3.0, -4.0, 6.0, -3.0]]], [[], [], 0]], [[[[37, 4.0, -4.0, 7.0, -1.0], [17, -3.0, -2.0, 0.0, -1.0], [1, -2.0, 3.0, -2.0, 5.0], [20, 5.0, -5.0, 7.0, -4.0], [8, 3.0, -3.0, 6.0, 0.0], [38, 4.0, -1.0, 5.0, -1.0]], [[37, 5.0, -4.0, 8.0, -1.0], [17, -2.0, -3.0, 1.0, -2.0], [1, -2.0, 4.0, -2.0, 6.0], [20, 6.0, -5.0, 8.0, -4.0], [8, 3.0, -3.0, 6.0, 0.0], [38, 8.0, 0.0, 9.0, 0.0]]], [[], [[8, 38]], 5]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[22, -1.0, -4.0, 0.0, -3.0], [36, 5.0, 5.0, 6.0, 8.0], [2, 1.0, -1.0, 3.0, 2.0], [25, -4.0, 0.0, -2.0, 2.0], [35, -1.0, -4.0, -1.0, -1.0]], [[22, -1.0, -5.0, 0.0, -4.0], [36, 9.0, 5.0, 10.0, 8.0], [2, 3.0, -1.0, 5.0, 2.0], [25, -4.0, 1.0, -2.0, 3.0], [35, -1.0, -5.0, -1.0, -2.0]]], [[], [], 0]], [[[[26, -3.0, -4.0, -1.0, -4.0], [16, 2.0, -2.0, 3.0, -2.0], [14, -5.0, 1.0, -3.0, 3.0], [4, 3.0, 1.0, 5.0, 2.0], [18, -2.0, -5.0, 1.0, -2.0]], [[26, -3.0, -4.0, -1.0, -4.0], [16, 3.0, -2.0, 4.0, -2.0], [14, -4.0, 1.0, -2.0, 3.0], [4, 2.0, 1.0, 4.0, 2.0], [18, -1.0, -5.0, 2.0, -2.0]]], [[], [], 2]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]]], [[[[[36, 5.0, 5.0, 6.0, 8.0], [6, 1.0, 5.0, 1.0, 5.0], [29, 3.0, -5.0, 5.0, -2.0], [1, 2.0, -5.0, 2.0, -3.0], [4, -1.0, -3.0, -1.0, -1.0], [10, -3.0, -2.0, -3.0, -2.0], [38, -2.0, 3.0, -1.0, 5.0]], [[36, 4.0, 4.0, 5.0, 7.0], [6, 3.0, 5.0, 3.0, 5.0], [29, 0.0, -5.0, 2.0, -2.0], [1, 1.0, -5.0, 1.0, -3.0], [4, -1.0, -3.0, -1.0, -1.0], [10, 1.0, -1.0, 1.0, -1.0], [38, 0.0, 3.0, 1.0, 5.0]]], [[[1, 29], [4, 10]], [[1, 6], [4, 10], [4, 38], [6, 29], [29, 36]], 24]], [[[[33, 5.0, -3.0, 6.0, -1.0], [7, 2.0, 0.0, 5.0, 3.0], [23, -5.0, -2.0, -3.0, 1.0], [31, 0.0, 0.0, 3.0, 0.0]], [[33, 7.0, -4.0, 8.0, -2.0], [7, 1.0, 0.0, 4.0, 3.0], [23, -8.0, -1.0, -6.0, 2.0], [31, -1.0, 0.0, 2.0, 0.0]]], [[], [[7, 33]], 1]], [[[[14, -1.0, -1.0, 0.0, 2.0], [10, -4.0, -1.0, -2.0, 1.0], [8, 2.0, -2.0, 2.0, 0.0], [39, -1.0, 0.0, 1.0, 1.0], [22, -1.0, 0.0, -1.0, 2.0], [20, -2.0, 0.0, 0.0, 3.0]], [[14, -2.0, -1.0, -1.0, 2.0], [10, -5.0, -1.0, -3.0, 1.0], [8, 2.0, -1.0, 2.0, 1.0], [39, -4.0, 0.0, -2.0, 1.0], [22, -4.0, -1.0, -4.0, 1.0], [20, -2.0, 0.0, 0.0, 3.0]]], [[[10, 22], [10, 39]], [[10, 20], [14, 22], [20, 22]], 12]], [[[[13, -4.0, 4.0, -3.0, 4.0], [6, 5.0, -4.0, 5.0, -1.0], [39, -4.0, -5.0, -4.0, -2.0], [34, 2.0, -4.0, 2.0, -4.0], [5, -5.0, 4.0, -3.0, 4.0]], [[13, -3.0, 4.0, -2.0, 4.0], [6, 5.0, -5.0, 5.0, -2.0], [39, -3.0, -5.0, -3.0, -2.0], [34, 2.0, -5.0, 2.0, -5.0], [5, -3.0, 3.0, -1.0, 3.0]]], [[], [], 1]], [[[[34, 1.0, -3.0, 3.0, -1.0], [18, -1.0, -3.0, 2.0, -3.0]], [[34, 1.0, -4.0, 3.0, -2.0], [18, 0.0, -2.0, 3.0, -2.0]]], [[], [], 0]], [[[[10, 0.0, -5.0, 1.0, -5.0], [12, -3.0, -3.0, 0.0, -2.0]], [[10, 1.0, -5.0, 2.0, -5.0], [12, -2.0, -2.0, 1.0, -1.0]]], [[], [], 0]], [[[[36, -2.0, -5.0, -1.0, -3.0], [28, 3.0, 5.0, 6.0, 5.0]], [[36, -2.0, -5.0, -1.0, -3.0], [28, 7.0, 4.0, 10.0, 4.0]]], [[], [], 0]], [[[[4, -5.0, -3.0, -3.0, 0.0], [9, -3.0, -1.0, -2.0, 1.0], [29, 5.0, 4.0, 6.0, 4.0], [33, 4.0, -5.0, 4.0, -4.0], [37, 5.0, -4.0, 7.0, -2.0], [27, 5.0, 4.0, 5.0, 7.0]], [[4, -4.0, -3.0, -2.0, 0.0], [9, -4.0, 0.0, -3.0, 2.0], [29, 7.0, 3.0, 8.0, 3.0], [33, 4.0, -5.0, 4.0, -4.0], [37, 6.0, -3.0, 8.0, -1.0], [27, 9.0, 4.0, 9.0, 7.0]]], [[], [[27, 29], [27, 37]], 8]]], [[[[[39, 0.0, -2.0, 0.0, -2.0], [7, 5.0, -5.0, 7.0, -3.0], [24, 5.0, 3.0, 8.0, 5.0], [19, -3.0, 3.0, -2.0, 4.0], [10, -1.0, 3.0, 0.0, 6.0], [38, 0.0, 4.0, 1.0, 6.0], [29, 3.0, 3.0, 3.0, 4.0], [4, 4.0, 3.0, 6.0, 5.0]], [[39, 0.0, -2.0, 0.0, -2.0], [7, 7.0, -4.0, 9.0, -2.0], [24, 5.0, 2.0, 8.0, 4.0], [19, -6.0, 2.0, -5.0, 3.0], [10, -1.0, 3.0, 0.0, 6.0], [38, 2.0, 4.0, 3.0, 6.0], [29, 5.0, 3.0, 5.0, 4.0], [4, 5.0, 2.0, 7.0, 4.0]]], [[[4, 29], [24, 29]], [[10, 38], [38, 39]], 7]], [[[[17, -5.0, 2.0, -5.0, 3.0], [36, 1.0, 5.0, 1.0, 8.0]], [[17, -6.0, 2.0, -6.0, 3.0], [36, 0.0, 4.0, 0.0, 7.0]]], [[], [], 0]], [[[[9, 0.0, 0.0, 1.0, 3.0], [28, 0.0, 1.0, 0.0, 2.0], [36, 5.0, -5.0, 8.0, -2.0]], [[9, -1.0, 1.0, 0.0, 4.0], [28, 0.0, 1.0, 0.0, 2.0], [36, 6.0, -6.0, 9.0, -3.0]]], [[], [], 0]], [[[[23, -2.0, 0.0, -1.0, 1.0], [39, -2.0, -3.0, -2.0, -3.0], [15, -1.0, -1.0, -1.0, 0.0]], [[23, 0.0, 0.0, 1.0, 1.0], [39, 0.0, -4.0, 0.0, -4.0], [15, -2.0, -1.0, -2.0, 0.0]]], [[], [[15, 23], [15, 39]], 6]], [[[[20, -5.0, -1.0, -5.0, 2.0], [7, 3.0, 0.0, 5.0, 1.0]], [[20, -5.0, -1.0, -5.0, 2.0], [7, 7.0, 0.0, 9.0, 1.0]]], [[], [], 0]], [[[[3, 5.0, 4.0, 6.0, 7.0], [21, 4.0, 2.0, 6.0, 2.0], [35, 4.0, -3.0, 6.0, 0.0], [14, -4.0, -5.0, -4.0, -5.0], [31, -2.0, 2.0, -1.0, 2.0], [20, 5.0, 3.0, 8.0, 5.0], [34, 1.0, 5.0, 2.0, 6.0]], [[3, 4.0, 4.0, 5.0, 7.0], [21, 5.0, 2.0, 7.0, 2.0], [35, 5.0, -3.0, 7.0, 0.0], [14, -2.0, -5.0, -2.0, -5.0], [31, -2.0, 3.0, -1.0, 3.0], [20, 5.0, 2.0, 8.0, 4.0], [34, 1.0, 6.0, 2.0, 7.0]]], [[], [], 3]], [[[[18, 0.0, -4.0, 2.0, -1.0], [27, 4.0, -1.0, 4.0, 2.0], [15, -3.0, 0.0, -3.0, 3.0], [31, -3.0, -3.0, 0.0, -2.0], [26, 2.0, 4.0, 2.0, 5.0]], [[18, 0.0, -5.0, 2.0, -2.0], [27, 3.0, 0.0, 3.0, 3.0], [15, -3.0, -1.0, -3.0, 2.0], [31, -6.0, -3.0, -3.0, -2.0], [26, 2.0, 4.0, 2.0, 5.0]]], [[], [[18, 31]], 2]], [[[[3, 1.0, -5.0, 2.0, -5.0], [32, 2.0, -5.0, 3.0, -3.0], [38, -3.0, 5.0, -1.0, 5.0], [1, 2.0, 3.0, 4.0, 3.0], [13, -3.0, -4.0, 0.0, -3.0]], [[3, 2.0, -4.0, 3.0, -4.0], [32, 2.0, -5.0, 3.0, -3.0], [38, -3.0, 5.0, -1.0, 5.0], [1, 3.0, 2.0, 5.0, 2.0], [13, -3.0, -5.0, 0.0, -4.0]]], [[], [], 1]]], [[[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[9, 3.0, -2.0, 4.0, -2.0], [24, 4.0, 0.0, 5.0, 0.0], [25, 4.0, 1.0, 5.0, 1.0]], [[9, 0.0, -3.0, 1.0, -3.0], [24, 6.0, 0.0, 7.0, 0.0], [25, 4.0, 2.0, 5.0, 2.0]]], [[], [[9, 24], [9, 25], [24, 25]], 5]], [[[[15, -4.0, -4.0, -2.0, -3.0], [33, -4.0, 1.0, -4.0, 4.0], [38, 3.0, -1.0, 5.0, 1.0]], [[15, -4.0, -5.0, -2.0, -4.0], [33, -2.0, 0.0, -2.0, 3.0], [38, 4.0, 0.0, 6.0, 2.0]]], [[], [], 0]], [[[[22, 1.0, -2.0, 3.0, 0.0], [16, -1.0, 0.0, 1.0, 1.0], [28, -2.0, -2.0, -2.0, -2.0], [29, -3.0, 0.0, 0.0, 0.0], [5, 1.0, -3.0, 1.0, 0.0], [1, -4.0, 2.0, -2.0, 2.0], [7, 5.0, -2.0, 6.0, -2.0]], [[22, -2.0, -2.0, 0.0, 0.0], [16, -1.0, -1.0, 1.0, 0.0], [28, -5.0, -1.0, -5.0, -1.0], [29, -2.0, 0.0, 1.0, 0.0], [5, -2.0, -3.0, -2.0, 0.0], [1, -7.0, 2.0, -5.0, 2.0], [7, 7.0, -2.0, 8.0, -2.0]]], [[[5, 29], [22, 29]], [[1, 29], [5, 16], [28, 29]], 11]], [[[[38, 2.0, -1.0, 4.0, -1.0], [13, -5.0, 2.0, -4.0, 2.0], [17, -1.0, -1.0, 1.0, -1.0], [22, 3.0, -5.0, 6.0, -5.0], [4, -1.0, 3.0, 0.0, 3.0], [12, 1.0, -5.0, 3.0, -4.0], [23, 1.0, -4.0, 2.0, -3.0], [15, -5.0, -2.0, -3.0, -1.0]], [[38, 2.0, -2.0, 4.0, -2.0], [13, -1.0, 2.0, 0.0, 2.0], [17, -4.0, -2.0, -2.0, -2.0], [22, 5.0, -6.0, 8.0, -6.0], [4, -4.0, 3.0, -3.0, 3.0], [12, 3.0, -6.0, 5.0, -5.0], [23, 1.0, -4.0, 2.0, -3.0], [15, -4.0, -2.0, -2.0, -1.0]]], [[[15, 17]], [[4, 13], [12, 17], [12, 23], [13, 15], [13, 17], [17, 23], [22, 38]], 21]], [[[[21, 2.0, 0.0, 4.0, 1.0], [38, -5.0, 0.0, -3.0, 2.0], [25, 2.0, -2.0, 5.0, 0.0], [1, 0.0, 2.0, 2.0, 4.0]], [[21, 1.0, -1.0, 3.0, 0.0], [38, -4.0, 0.0, -2.0, 2.0], [25, 2.0, -2.0, 5.0, 0.0], [1, 0.0, 2.0, 2.0, 4.0]]], [[], [], 0]], [[[[16, -2.0, -4.0, -1.0, -4.0], [20, -2.0, -3.0, 0.0, -1.0], [7, -4.0, -3.0, -2.0, -2.0]], [[16, -2.0, -4.0, -1.0, -4.0], [20, -5.0, -4.0, -3.0, -2.0], [7, -4.0, -3.0, -2.0, -2.0]]], [[], [[16, 20]], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[7, 4.0, -2.0, 7.0, -2.0], [28, -5.0, 5.0, -3.0, 6.0], [34, 0.0, 4.0, 0.0, 5.0], [22, 1.0, 0.0, 2.0, 0.0], [17, 0.0, -5.0, 1.0, -3.0], [29, -3.0, 0.0, -1.0, 0.0], [24, 3.0, 2.0, 3.0, 3.0], [31, 1.0, -1.0, 2.0, -1.0], [8, -4.0, 1.0, -4.0, 3.0], [12, -2.0, -1.0, -2.0, 1.0]], [[7, 6.0, -2.0, 9.0, -2.0], [28, -5.0, 5.0, -3.0, 6.0], [34, 0.0, 4.0, 0.0, 5.0], [22, 5.0, 0.0, 6.0, 0.0], [17, 2.0, -4.0, 3.0, -2.0], [29, -3.0, -1.0, -1.0, -1.0], [24, 5.0, 2.0, 5.0, 3.0], [31, 3.0, -1.0, 4.0, -1.0], [8, -2.0, 1.0, -2.0, 3.0], [12, 2.0, -2.0, 2.0, 0.0]]], [[[12, 17]], [[8, 28], [12, 29], [12, 34], [17, 22], [17, 34], [22, 31]], 20]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[23, 1.0, 0.0, 2.0, 1.0], [30, 5.0, -2.0, 5.0, -1.0], [16, 3.0, 5.0, 6.0, 8.0], [2, -3.0, 2.0, 0.0, 2.0]], [[23, 0.0, 0.0, 1.0, 1.0], [30, 7.0, -2.0, 7.0, -1.0], [16, 5.0, 4.0, 8.0, 7.0], [2, -6.0, 3.0, -3.0, 3.0]]], [[], [], 0]], [[[[25, -5.0, -2.0, -5.0, -2.0], [17, 3.0, 5.0, 3.0, 8.0], [1, 3.0, -2.0, 6.0, 1.0]], [[25, -5.0, -2.0, -5.0, -2.0], [17, 5.0, 5.0, 5.0, 8.0], [1, 4.0, -1.0, 7.0, 2.0]]], [[], [], 0]], [[[[16, -2.0, -3.0, 1.0, -2.0], [38, -2.0, 4.0, 0.0, 4.0], [23, 3.0, 1.0, 4.0, 2.0]], [[16, -2.0, -2.0, 1.0, -1.0], [38, -1.0, 5.0, 1.0, 5.0], [23, 3.0, 0.0, 4.0, 1.0]]], [[], [], 0]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]], [[[[5, -2.0, 4.0, -2.0, 4.0], [32, -3.0, 2.0, -2.0, 2.0], [31, -3.0, -2.0, -3.0, 0.0], [26, 3.0, 4.0, 5.0, 6.0], [28, -4.0, 5.0, -3.0, 6.0], [30, 5.0, -1.0, 8.0, 2.0], [39, 5.0, -2.0, 6.0, 0.0], [20, 4.0, 1.0, 4.0, 1.0], [1, 0.0, -1.0, 1.0, -1.0]], [[5, 2.0, 4.0, 2.0, 4.0], [32, -3.0, 2.0, -2.0, 2.0], [31, -6.0, -1.0, -6.0, 1.0], [26, 2.0, 4.0, 4.0, 6.0], [28, -2.0, 6.0, -1.0, 7.0], [30, 9.0, 0.0, 12.0, 3.0], [39, 6.0, -2.0, 7.0, 0.0], [20, 6.0, 1.0, 6.0, 1.0], [1, -1.0, -1.0, 0.0, -1.0]]], [[[5, 26]], [[1, 5], [5, 32], [20, 26], [26, 30], [26, 39], [28, 31], [30, 39], [31, 32]], 21]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"1d3210d36143840cd1b0238a07d8d679da4a135ab48e882b8654afcb080e4f9c","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(prev, curr):\n    old = {b[0]: b for b in prev}\n    new = {b[0]: b for b in curr}\n    E = []\n    for i, b in new.items():\n        E.append([b[1], 0, i])\n        E.append([b[3], 1, i])\n    E.sort()\n    for e in E:\n        b = new[e[2]]\n        e[0] = b[1] if e[1] == 0 else b[3]\n    def yover(a, c):\n        return new[a][2] <= new[c][4] and new[c][2] <= new[a][4]\n    begins, ends = set(), set()\n    swaps = 0\n    for i in range(1, len(E)):\n        j = i\n        while j > 0 and (E[j - 1][0], E[j - 1][1]) > (E[j][0], E[j][1]):\n            e, f = E[j], E[j - 1]\n            E[j - 1], E[j] = e, f\n            swaps += 1\n            p = (min(e[2], f[2]), max(e[2], f[2]))\n            if e[1] == 0 and f[1] == 1:\n                if yover(e[2], f[2]):\n                    begins.add(p)\n            elif e[1] == 1 and f[1] == 0:\n                ends.add(p)\n            j -= 1\n    return [sorted(list(p) for p in begins), sorted(list(p) for p in ends), swaps]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\nfixtures = [[[[[[28, 5.0, 2.0, 7.0, 2.0], [8, -1.0, -1.0, 0.0, 0.0]], [[28, 7.0, 1.0, 9.0, 1.0], [8, -4.0, -2.0, -3.0, -1.0]]], [[], [], 0]], [[[[10, 1.0, -5.0, 3.0, -4.0], [15, -2.0, 4.0, -2.0, 7.0], [19, -3.0, -1.0, 0.0, 1.0], [14, 1.0, 1.0, 4.0, 3.0], [22, 3.0, -3.0, 3.0, -1.0]], [[10, -2.0, -5.0, 0.0, -4.0], [15, 0.0, 4.0, 0.0, 7.0], [19, 1.0, 0.0, 4.0, 2.0], [14, 1.0, 1.0, 4.0, 3.0], [22, 2.0, -4.0, 2.0, -2.0]]], [[[14, 19]], [[10, 14], [10, 19], [10, 22], [15, 19]], 13]], [[[[15, -4.0, 5.0, -4.0, 8.0], [26, -1.0, 3.0, -1.0, 4.0], [31, 0.0, -2.0, 1.0, 0.0], [33, 3.0, -3.0, 6.0, -2.0]], [[15, -7.0, 5.0, -7.0, 8.0], [26, -1.0, 2.0, -1.0, 3.0], [31, 0.0, -2.0, 1.0, 0.0], [33, 3.0, -4.0, 6.0, -3.0]]], [[], [], 0]], [[[[37, 4.0, -4.0, 7.0, -1.0], [17, -3.0, -2.0, 0.0, -1.0], [1, -2.0, 3.0, -2.0, 5.0], [20, 5.0, -5.0, 7.0, -4.0], [8, 3.0, -3.0, 6.0, 0.0], [38, 4.0, -1.0, 5.0, -1.0]], [[37, 5.0, -4.0, 8.0, -1.0], [17, -2.0, -3.0, 1.0, -2.0], [1, -2.0, 4.0, -2.0, 6.0], [20, 6.0, -5.0, 8.0, -4.0], [8, 3.0, -3.0, 6.0, 0.0], [38, 8.0, 0.0, 9.0, 0.0]]], [[], [[8, 38]], 5]], [[[[35, -4.0, 0.0, -3.0, 1.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 5.0, -2.0, 5.0, 1.0], [25, 4.0, -1.0, 4.0, 1.0]], [[35, -7.0, -1.0, -6.0, 0.0], [4, -4.0, 0.0, -4.0, 3.0], [36, 7.0, -2.0, 7.0, 1.0], [25, 4.0, 0.0, 4.0, 2.0]]], [[], [[4, 35]], 3]], [[[[22, -1.0, -4.0, 0.0, -3.0], [36, 5.0, 5.0, 6.0, 8.0], [2, 1.0, -1.0, 3.0, 2.0], [25, -4.0, 0.0, -2.0, 2.0], [35, -1.0, -4.0, -1.0, -1.0]], [[22, -1.0, -5.0, 0.0, -4.0], [36, 9.0, 5.0, 10.0, 8.0], [2, 3.0, -1.0, 5.0, 2.0], [25, -4.0, 1.0, -2.0, 3.0], [35, -1.0, -5.0, -1.0, -2.0]]], [[], [], 0]], [[[[26, -3.0, -4.0, -1.0, -4.0], [16, 2.0, -2.0, 3.0, -2.0], [14, -5.0, 1.0, -3.0, 3.0], [4, 3.0, 1.0, 5.0, 2.0], [18, -2.0, -5.0, 1.0, -2.0]], [[26, -3.0, -4.0, -1.0, -4.0], [16, 3.0, -2.0, 4.0, -2.0], [14, -4.0, 1.0, -2.0, 3.0], [4, 2.0, 1.0, 4.0, 2.0], [18, -1.0, -5.0, 2.0, -2.0]]], [[], [], 2]], [[[[37, 3.0, -2.0, 5.0, -1.0], [14, -2.0, -4.0, 0.0, -2.0], [18, -5.0, 4.0, -2.0, 5.0]], [[37, 5.0, -1.0, 7.0, 0.0], [14, -3.0, -4.0, -1.0, -2.0], [18, -6.0, 4.0, -3.0, 5.0]]], [[], [], 0]]], [[[[[36, 5.0, 5.0, 6.0, 8.0], [6, 1.0, 5.0, 1.0, 5.0], [29, 3.0, -5.0, 5.0, -2.0], [1, 2.0, -5.0, 2.0, -3.0], [4, -1.0, -3.0, -1.0, -1.0], [10, -3.0, -2.0, -3.0, -2.0], [38, -2.0, 3.0, -1.0, 5.0]], [[36, 4.0, 4.0, 5.0, 7.0], [6, 3.0, 5.0, 3.0, 5.0], [29, 0.0, -5.0, 2.0, -2.0], [1, 1.0, -5.0, 1.0, -3.0], [4, -1.0, -3.0, -1.0, -1.0], [10, 1.0, -1.0, 1.0, -1.0], [38, 0.0, 3.0, 1.0, 5.0]]], [[[1, 29], [4, 10]], [[1, 6], [4, 10], [4, 38], [6, 29], [29, 36]], 24]], [[[[33, 5.0, -3.0, 6.0, -1.0], [7, 2.0, 0.0, 5.0, 3.0], [23, -5.0, -2.0, -3.0, 1.0], [31, 0.0, 0.0, 3.0, 0.0]], [[33, 7.0, -4.0, 8.0, -2.0], [7, 1.0, 0.0, 4.0, 3.0], [23, -8.0, -1.0, -6.0, 2.0], [31, -1.0, 0.0, 2.0, 0.0]]], [[], [[7, 33]], 1]], [[[[14, -1.0, -1.0, 0.0, 2.0], [10, -4.0, -1.0, -2.0, 1.0], [8, 2.0, -2.0, 2.0, 0.0], [39, -1.0, 0.0, 1.0, 1.0], [22, -1.0, 0.0, -1.0, 2.0], [20, -2.0, 0.0, 0.0, 3.0]], [[14, -2.0, -1.0, -1.0, 2.0], [10, -5.0, -1.0, -3.0, 1.0], [8, 2.0, -1.0, 2.0, 1.0], [39, -4.0, 0.0, -2.0, 1.0], [22, -4.0, -1.0, -4.0, 1.0], [20, -2.0, 0.0, 0.0, 3.0]]], [[[10, 22], [10, 39]], [[10, 20], [14, 22], [20, 22]], 12]], [[[[13, -4.0, 4.0, -3.0, 4.0], [6, 5.0, -4.0, 5.0, -1.0], [39, -4.0, -5.0, -4.0, -2.0], [34, 2.0, -4.0, 2.0, -4.0], [5, -5.0, 4.0, -3.0, 4.0]], [[13, -3.0, 4.0, -2.0, 4.0], [6, 5.0, -5.0, 5.0, -2.0], [39, -3.0, -5.0, -3.0, -2.0], [34, 2.0, -5.0, 2.0, -5.0], [5, -3.0, 3.0, -1.0, 3.0]]], [[], [], 1]], [[[[34, 1.0, -3.0, 3.0, -1.0], [18, -1.0, -3.0, 2.0, -3.0]], [[34, 1.0, -4.0, 3.0, -2.0], [18, 0.0, -2.0, 3.0, -2.0]]], [[], [], 0]], [[[[10, 0.0, -5.0, 1.0, -5.0], [12, -3.0, -3.0, 0.0, -2.0]], [[10, 1.0, -5.0, 2.0, -5.0], [12, -2.0, -2.0, 1.0, -1.0]]], [[], [], 0]], [[[[36, -2.0, -5.0, -1.0, -3.0], [28, 3.0, 5.0, 6.0, 5.0]], [[36, -2.0, -5.0, -1.0, -3.0], [28, 7.0, 4.0, 10.0, 4.0]]], [[], [], 0]], [[[[4, -5.0, -3.0, -3.0, 0.0], [9, -3.0, -1.0, -2.0, 1.0], [29, 5.0, 4.0, 6.0, 4.0], [33, 4.0, -5.0, 4.0, -4.0], [37, 5.0, -4.0, 7.0, -2.0], [27, 5.0, 4.0, 5.0, 7.0]], [[4, -4.0, -3.0, -2.0, 0.0], [9, -4.0, 0.0, -3.0, 2.0], [29, 7.0, 3.0, 8.0, 3.0], [33, 4.0, -5.0, 4.0, -4.0], [37, 6.0, -3.0, 8.0, -1.0], [27, 9.0, 4.0, 9.0, 7.0]]], [[], [[27, 29], [27, 37]], 8]]], [[[[[39, 0.0, -2.0, 0.0, -2.0], [7, 5.0, -5.0, 7.0, -3.0], [24, 5.0, 3.0, 8.0, 5.0], [19, -3.0, 3.0, -2.0, 4.0], [10, -1.0, 3.0, 0.0, 6.0], [38, 0.0, 4.0, 1.0, 6.0], [29, 3.0, 3.0, 3.0, 4.0], [4, 4.0, 3.0, 6.0, 5.0]], [[39, 0.0, -2.0, 0.0, -2.0], [7, 7.0, -4.0, 9.0, -2.0], [24, 5.0, 2.0, 8.0, 4.0], [19, -6.0, 2.0, -5.0, 3.0], [10, -1.0, 3.0, 0.0, 6.0], [38, 2.0, 4.0, 3.0, 6.0], [29, 5.0, 3.0, 5.0, 4.0], [4, 5.0, 2.0, 7.0, 4.0]]], [[[4, 29], [24, 29]], [[10, 38], [38, 39]], 7]], [[[[17, -5.0, 2.0, -5.0, 3.0], [36, 1.0, 5.0, 1.0, 8.0]], [[17, -6.0, 2.0, -6.0, 3.0], [36, 0.0, 4.0, 0.0, 7.0]]], [[], [], 0]], [[[[9, 0.0, 0.0, 1.0, 3.0], [28, 0.0, 1.0, 0.0, 2.0], [36, 5.0, -5.0, 8.0, -2.0]], [[9, -1.0, 1.0, 0.0, 4.0], [28, 0.0, 1.0, 0.0, 2.0], [36, 6.0, -6.0, 9.0, -3.0]]], [[], [], 0]], [[[[23, -2.0, 0.0, -1.0, 1.0], [39, -2.0, -3.0, -2.0, -3.0], [15, -1.0, -1.0, -1.0, 0.0]], [[23, 0.0, 0.0, 1.0, 1.0], [39, 0.0, -4.0, 0.0, -4.0], [15, -2.0, -1.0, -2.0, 0.0]]], [[], [[15, 23], [15, 39]], 6]], [[[[20, -5.0, -1.0, -5.0, 2.0], [7, 3.0, 0.0, 5.0, 1.0]], [[20, -5.0, -1.0, -5.0, 2.0], [7, 7.0, 0.0, 9.0, 1.0]]], [[], [], 0]], [[[[3, 5.0, 4.0, 6.0, 7.0], [21, 4.0, 2.0, 6.0, 2.0], [35, 4.0, -3.0, 6.0, 0.0], [14, -4.0, -5.0, -4.0, -5.0], [31, -2.0, 2.0, -1.0, 2.0], [20, 5.0, 3.0, 8.0, 5.0], [34, 1.0, 5.0, 2.0, 6.0]], [[3, 4.0, 4.0, 5.0, 7.0], [21, 5.0, 2.0, 7.0, 2.0], [35, 5.0, -3.0, 7.0, 0.0], [14, -2.0, -5.0, -2.0, -5.0], [31, -2.0, 3.0, -1.0, 3.0], [20, 5.0, 2.0, 8.0, 4.0], [34, 1.0, 6.0, 2.0, 7.0]]], [[], [], 3]], [[[[18, 0.0, -4.0, 2.0, -1.0], [27, 4.0, -1.0, 4.0, 2.0], [15, -3.0, 0.0, -3.0, 3.0], [31, -3.0, -3.0, 0.0, -2.0], [26, 2.0, 4.0, 2.0, 5.0]], [[18, 0.0, -5.0, 2.0, -2.0], [27, 3.0, 0.0, 3.0, 3.0], [15, -3.0, -1.0, -3.0, 2.0], [31, -6.0, -3.0, -3.0, -2.0], [26, 2.0, 4.0, 2.0, 5.0]]], [[], [[18, 31]], 2]], [[[[3, 1.0, -5.0, 2.0, -5.0], [32, 2.0, -5.0, 3.0, -3.0], [38, -3.0, 5.0, -1.0, 5.0], [1, 2.0, 3.0, 4.0, 3.0], [13, -3.0, -4.0, 0.0, -3.0]], [[3, 2.0, -4.0, 3.0, -4.0], [32, 2.0, -5.0, 3.0, -3.0], [38, -3.0, 5.0, -1.0, 5.0], [1, 3.0, 2.0, 5.0, 2.0], [13, -3.0, -5.0, 0.0, -4.0]]], [[], [], 1]]], [[[[[24, -2.0, -3.0, 0.0, -1.0], [32, 0.0, -3.0, 2.0, 0.0]], [[24, 2.0, -2.0, 4.0, 0.0], [32, 4.0, -3.0, 6.0, 0.0]]], [[], [], 0]], [[[[9, 3.0, -2.0, 4.0, -2.0], [24, 4.0, 0.0, 5.0, 0.0], [25, 4.0, 1.0, 5.0, 1.0]], [[9, 0.0, -3.0, 1.0, -3.0], [24, 6.0, 0.0, 7.0, 0.0], [25, 4.0, 2.0, 5.0, 2.0]]], [[], [[9, 24], [9, 25], [24, 25]], 5]], [[[[15, -4.0, -4.0, -2.0, -3.0], [33, -4.0, 1.0, -4.0, 4.0], [38, 3.0, -1.0, 5.0, 1.0]], [[15, -4.0, -5.0, -2.0, -4.0], [33, -2.0, 0.0, -2.0, 3.0], [38, 4.0, 0.0, 6.0, 2.0]]], [[], [], 0]], [[[[22, 1.0, -2.0, 3.0, 0.0], [16, -1.0, 0.0, 1.0, 1.0], [28, -2.0, -2.0, -2.0, -2.0], [29, -3.0, 0.0, 0.0, 0.0], [5, 1.0, -3.0, 1.0, 0.0], [1, -4.0, 2.0, -2.0, 2.0], [7, 5.0, -2.0, 6.0, -2.0]], [[22, -2.0, -2.0, 0.0, 0.0], [16, -1.0, -1.0, 1.0, 0.0], [28, -5.0, -1.0, -5.0, -1.0], [29, -2.0, 0.0, 1.0, 0.0], [5, -2.0, -3.0, -2.0, 0.0], [1, -7.0, 2.0, -5.0, 2.0], [7, 7.0, -2.0, 8.0, -2.0]]], [[[5, 29], [22, 29]], [[1, 29], [5, 16], [28, 29]], 11]], [[[[38, 2.0, -1.0, 4.0, -1.0], [13, -5.0, 2.0, -4.0, 2.0], [17, -1.0, -1.0, 1.0, -1.0], [22, 3.0, -5.0, 6.0, -5.0], [4, -1.0, 3.0, 0.0, 3.0], [12, 1.0, -5.0, 3.0, -4.0], [23, 1.0, -4.0, 2.0, -3.0], [15, -5.0, -2.0, -3.0, -1.0]], [[38, 2.0, -2.0, 4.0, -2.0], [13, -1.0, 2.0, 0.0, 2.0], [17, -4.0, -2.0, -2.0, -2.0], [22, 5.0, -6.0, 8.0, -6.0], [4, -4.0, 3.0, -3.0, 3.0], [12, 3.0, -6.0, 5.0, -5.0], [23, 1.0, -4.0, 2.0, -3.0], [15, -4.0, -2.0, -2.0, -1.0]]], [[[15, 17]], [[4, 13], [12, 17], [12, 23], [13, 15], [13, 17], [17, 23], [22, 38]], 21]], [[[[21, 2.0, 0.0, 4.0, 1.0], [38, -5.0, 0.0, -3.0, 2.0], [25, 2.0, -2.0, 5.0, 0.0], [1, 0.0, 2.0, 2.0, 4.0]], [[21, 1.0, -1.0, 3.0, 0.0], [38, -4.0, 0.0, -2.0, 2.0], [25, 2.0, -2.0, 5.0, 0.0], [1, 0.0, 2.0, 2.0, 4.0]]], [[], [], 0]], [[[[16, -2.0, -4.0, -1.0, -4.0], [20, -2.0, -3.0, 0.0, -1.0], [7, -4.0, -3.0, -2.0, -2.0]], [[16, -2.0, -4.0, -1.0, -4.0], [20, -5.0, -4.0, -3.0, -2.0], [7, -4.0, -3.0, -2.0, -2.0]]], [[], [[16, 20]], 5]], [[[[7, 3.0, -1.0, 3.0, 0.0], [27, -5.0, -5.0, -2.0, -2.0], [15, 3.0, 5.0, 5.0, 6.0], [31, -2.0, -2.0, -2.0, -1.0], [26, 4.0, 1.0, 4.0, 3.0], [30, 3.0, -4.0, 5.0, -3.0], [29, 4.0, 4.0, 7.0, 4.0], [1, -5.0, -5.0, -3.0, -3.0], [39, 3.0, -2.0, 3.0, 1.0]], [[7, 7.0, -1.0, 7.0, 0.0], [27, -4.0, -5.0, -1.0, -2.0], [15, 2.0, 4.0, 4.0, 5.0], [31, -5.0, -1.0, -5.0, 0.0], [26, 3.0, 1.0, 3.0, 3.0], [30, 4.0, -3.0, 6.0, -2.0], [29, 6.0, 3.0, 9.0, 3.0], [1, -1.0, -5.0, 1.0, -3.0], [39, 5.0, -3.0, 5.0, 0.0]]], [[], [[1, 31], [7, 15], [7, 26], [7, 30], [7, 39], [15, 29], [15, 39], [26, 29], [26, 30], [26, 39], [27, 31]], 34]]], [[[[[28, 2.0, 2.0, 5.0, 2.0], [24, -3.0, 4.0, -3.0, 4.0], [29, -5.0, 4.0, -4.0, 5.0], [10, 1.0, 1.0, 4.0, 2.0], [33, -2.0, -4.0, -1.0, -3.0], [12, 2.0, 3.0, 2.0, 3.0], [39, -5.0, -3.0, -2.0, -2.0], [1, 3.0, -5.0, 4.0, -4.0]], [[28, 2.0, 2.0, 5.0, 2.0], [24, -4.0, 5.0, -4.0, 5.0], [29, -6.0, 3.0, -5.0, 4.0], [10, 3.0, 1.0, 6.0, 2.0], [33, -3.0, -4.0, -2.0, -3.0], [12, 4.0, 3.0, 4.0, 3.0], [39, -3.0, -2.0, 0.0, -1.0], [1, 2.0, -5.0, 3.0, -4.0]]], [[], [[1, 12], [24, 39], [29, 39]], 12]], [[[[7, 4.0, -2.0, 7.0, -2.0], [28, -5.0, 5.0, -3.0, 6.0], [34, 0.0, 4.0, 0.0, 5.0], [22, 1.0, 0.0, 2.0, 0.0], [17, 0.0, -5.0, 1.0, -3.0], [29, -3.0, 0.0, -1.0, 0.0], [24, 3.0, 2.0, 3.0, 3.0], [31, 1.0, -1.0, 2.0, -1.0], [8, -4.0, 1.0, -4.0, 3.0], [12, -2.0, -1.0, -2.0, 1.0]], [[7, 6.0, -2.0, 9.0, -2.0], [28, -5.0, 5.0, -3.0, 6.0], [34, 0.0, 4.0, 0.0, 5.0], [22, 5.0, 0.0, 6.0, 0.0], [17, 2.0, -4.0, 3.0, -2.0], [29, -3.0, -1.0, -1.0, -1.0], [24, 5.0, 2.0, 5.0, 3.0], [31, 3.0, -1.0, 4.0, -1.0], [8, -2.0, 1.0, -2.0, 3.0], [12, 2.0, -2.0, 2.0, 0.0]]], [[[12, 17]], [[8, 28], [12, 29], [12, 34], [17, 22], [17, 34], [22, 31]], 20]], [[[[9, 4.0, -4.0, 5.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 5.0, 3.0, 5.0, 5.0], [17, 0.0, 2.0, 0.0, 2.0], [24, 5.0, 0.0, 6.0, 2.0], [21, -1.0, -3.0, 2.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -4.0, -4.0, -4.0, -1.0], [18, 3.0, 4.0, 6.0, 5.0], [8, 2.0, 3.0, 4.0, 5.0]], [[9, 6.0, -4.0, 7.0, -3.0], [28, -4.0, 1.0, -4.0, 3.0], [22, 9.0, 4.0, 9.0, 6.0], [17, 0.0, 1.0, 0.0, 1.0], [24, 9.0, -1.0, 10.0, 1.0], [21, -4.0, -3.0, -1.0, -3.0], [6, 3.0, -3.0, 5.0, -2.0], [32, -7.0, -5.0, -7.0, -2.0], [18, 2.0, 3.0, 5.0, 4.0], [8, 6.0, 3.0, 8.0, 5.0]]], [[], [[6, 8], [6, 9], [6, 22], [6, 24], [8, 18], [8, 21], [9, 18], [9, 22], [9, 24], [17, 21], [18, 22], [18, 24], [28, 32]], 25]], [[[[23, 1.0, 0.0, 2.0, 1.0], [30, 5.0, -2.0, 5.0, -1.0], [16, 3.0, 5.0, 6.0, 8.0], [2, -3.0, 2.0, 0.0, 2.0]], [[23, 0.0, 0.0, 1.0, 1.0], [30, 7.0, -2.0, 7.0, -1.0], [16, 5.0, 4.0, 8.0, 7.0], [2, -6.0, 3.0, -3.0, 3.0]]], [[], [], 0]], [[[[25, -5.0, -2.0, -5.0, -2.0], [17, 3.0, 5.0, 3.0, 8.0], [1, 3.0, -2.0, 6.0, 1.0]], [[25, -5.0, -2.0, -5.0, -2.0], [17, 5.0, 5.0, 5.0, 8.0], [1, 4.0, -1.0, 7.0, 2.0]]], [[], [], 0]], [[[[16, -2.0, -3.0, 1.0, -2.0], [38, -2.0, 4.0, 0.0, 4.0], [23, 3.0, 1.0, 4.0, 2.0]], [[16, -2.0, -2.0, 1.0, -1.0], [38, -1.0, 5.0, 1.0, 5.0], [23, 3.0, 0.0, 4.0, 1.0]]], [[], [], 0]], [[[[20, -3.0, 1.0, -1.0, 4.0], [37, 3.0, 1.0, 4.0, 1.0], [3, 5.0, -1.0, 5.0, 2.0], [12, -4.0, 2.0, -4.0, 4.0], [21, -1.0, -2.0, 2.0, -1.0], [33, 2.0, 2.0, 5.0, 3.0], [6, 1.0, -2.0, 2.0, 0.0], [36, 3.0, 0.0, 3.0, 3.0]], [[20, 1.0, 0.0, 3.0, 3.0], [37, 4.0, 1.0, 5.0, 1.0], [3, 4.0, -1.0, 4.0, 2.0], [12, -5.0, 3.0, -5.0, 5.0], [21, -1.0, -1.0, 2.0, 0.0], [33, 1.0, 2.0, 4.0, 3.0], [6, 1.0, -3.0, 2.0, -1.0], [36, 0.0, 1.0, 0.0, 4.0]]], [[[3, 37], [20, 33], [20, 36]], [[6, 36], [20, 36], [33, 36], [36, 37]], 21]], [[[[5, -2.0, 4.0, -2.0, 4.0], [32, -3.0, 2.0, -2.0, 2.0], [31, -3.0, -2.0, -3.0, 0.0], [26, 3.0, 4.0, 5.0, 6.0], [28, -4.0, 5.0, -3.0, 6.0], [30, 5.0, -1.0, 8.0, 2.0], [39, 5.0, -2.0, 6.0, 0.0], [20, 4.0, 1.0, 4.0, 1.0], [1, 0.0, -1.0, 1.0, -1.0]], [[5, 2.0, 4.0, 2.0, 4.0], [32, -3.0, 2.0, -2.0, 2.0], [31, -6.0, -1.0, -6.0, 1.0], [26, 2.0, 4.0, 4.0, 6.0], [28, -2.0, 6.0, -1.0, 7.0], [30, 9.0, 0.0, 12.0, 3.0], [39, 6.0, -2.0, 7.0, 0.0], [20, 6.0, 1.0, 6.0, 1.0], [1, -1.0, -1.0, 0.0, -1.0]]], [[[5, 26]], [[1, 5], [5, 32], [20, 26], [26, 30], [26, 39], [28, 31], [30, 39], [31, 32]], 21]]]]\nfor i, (args, expected) in enumerate(fixtures[N-1]):\n    check(\"case %d\" % i, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic bounded teaching model with stipulated toy conventions; not a production physics engine or spatial index. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-collision_detection_broadphase-incremental-sap-swaps-seed-ordering","generated_at":"2026-09-29T14:51:02.329346+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Broadphase stages decide which object pairs ever reach narrowphase; a wrong boundary, ordering or bookkeeping rule silently drops real contacts or floods the solver with false candidates.","root_cause":"The endpoints are built from curr instead of prev.","sha256":"bc7fda6f14a4c6c37ff4a45316428bfae728608335baac44101f2aa1a7b6f51b","title":"Endpoint array is seeded from the new frame · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":45.671,"exit_code":1,"observations":[{"actual":[[],[],0],"check":"case 0","expected":[[],[],0],"passed":true},{"actual":[[[14,19]],[[14,15]],10],"check":"case 1","expected":[[[14,19]],[[10,14],[10,19],[10,22],[15,19]],13],"passed":false},{"actual":[[],[],0],"check":"case 2","expected":[[],[],0],"passed":true},{"actual":[[[8,17],[8,37],[20,37]],[[8,17]],11],"check":"case 3","expected":[[],[[8,38]],5],"passed":false},{"actual":[[[4,35],[25,35]],[[4,35],[25,35]],8],"check":"case 4","expected":[[],[[4,35]],3],"passed":false},{"actual":[[[2,25],[22,35]],[[2,22],[2,25],[2,35],[22,25]],18],"check":"case 5","expected":[[],[],0],"passed":false},{"actual":[[[4,14],[16,18],[18,26]],[[4,14],[4,26],[16,18],[16,26]],24],"check":"case 6","expected":[[],[],2],"passed":false},{"actual":[[],[],3],"check":"case 7","expected":[[],[],0],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[[14, 19]], [[14, 15]], 10], \"expected\": [[[14, 19]], [[10, 14], [10, 19], [10, 22], [15, 19]], 13], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[[8, 17], [8, 37], [20, 37]], [[8, 17]], 11], \"expected\": [[], [[8, 38]], 5], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[[4, 35], [25, 35]], [[4, 35], [25, 35]], 8], \"expected\": [[], [[4, 35]], 3], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[[2, 25], [22, 35]], [[2, 22], [2, 25], [2, 35], [22, 25]], 18], \"expected\": [[], [], 0], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[[4, 14], [16, 18], [18, 26]], [[4, 14], [4, 26], [16, 18], [16, 26]], 24], \"expected\": [[], [], 2], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[], [], 3], \"expected\": [[], [], 0], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":44.87,"exit_code":1,"observations":[{"actual":[[],[],0],"check":"case 0","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 1","expected":[[[14,19]],[[10,14],[10,19],[10,22],[15,19]],13],"passed":false},{"actual":[[],[],0],"check":"case 2","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 3","expected":[[],[[8,38]],5],"passed":false},{"actual":[[],[],0],"check":"case 4","expected":[[],[[4,35]],3],"passed":false},{"actual":[[],[],0],"check":"case 5","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 6","expected":[[],[],2],"passed":false},{"actual":[[],[],0],"check":"case 7","expected":[[],[],0],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 1\", \"actual\": [[], [], 0], \"expected\": [[[14, 19]], [[10, 14], [10, 19], [10, 22], [15, 19]], 13], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], [], 0], \"expected\": [[], [[8, 38]], 5], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [[4, 35]], 3], \"passed\": false}, {\"check\": \"case 5\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 6\", \"actual\": [[], [], 0], \"expected\": [[], [], 2], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}