{"abstract":"Boxes that move into touching contact never begin a pair.","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":"Ordering max before min on ties treats touching as separated.","family":"w2-collision_detection_broadphase-incremental-sap-swaps-endpoint-comparison-key","id":"FA-87786","implementations":{"attempt":{"sha256":"eab85b27385f8b5273bde67f0cf4de943218cf8464972d97dedc5b8428cb81b7","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()\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 = [[[[[[38, -5.0, 2.0, -4.0, 4.0], [19, -4.0, 5.0, -4.0, 5.0], [27, -2.0, -5.0, -2.0, -3.0], [21, -2.0, -2.0, 1.0, 0.0], [12, 2.0, -5.0, 5.0, -3.0]], [[38, -1.0, 3.0, 0.0, 5.0], [19, -5.0, 5.0, -5.0, 5.0], [27, -5.0, -4.0, -5.0, -2.0], [21, 2.0, -3.0, 5.0, -1.0], [12, 6.0, -4.0, 9.0, -2.0]]], [[], [[19, 38], [21, 27], [27, 38]], 9]], [[[[22, 2.0, 1.0, 3.0, 1.0], [28, 3.0, 0.0, 4.0, 0.0], [21, -2.0, -2.0, 1.0, -1.0], [33, -1.0, 1.0, 0.0, 2.0], [11, 2.0, 5.0, 5.0, 5.0], [18, -1.0, 1.0, -1.0, 1.0]], [[22, 6.0, 1.0, 7.0, 1.0], [28, 5.0, 0.0, 6.0, 0.0], [21, 0.0, -3.0, 3.0, -2.0], [33, -4.0, 1.0, -3.0, 2.0], [11, 6.0, 5.0, 9.0, 5.0], [18, 0.0, 2.0, 0.0, 2.0]]], [[], [[18, 33], [21, 33]], 8]], [[[[36, 4.0, -3.0, 4.0, -2.0], [30, 5.0, 1.0, 5.0, 1.0]], [[36, 4.0, -3.0, 4.0, -2.0], [30, 5.0, 1.0, 5.0, 1.0]]], [[], [], 0]], [[[[3, 3.0, 0.0, 4.0, 3.0], [1, 4.0, -1.0, 6.0, 1.0]], [[3, 0.0, 1.0, 1.0, 4.0], [1, 1.0, -1.0, 3.0, 1.0]]], [[], [], 0]], [[[[5, -4.0, -1.0, -2.0, 0.0], [15, 2.0, -2.0, 5.0, -2.0]], [[5, -4.0, -1.0, -2.0, 0.0], [15, 1.0, -3.0, 4.0, -3.0]]], [[], [], 0]], [[[[20, 1.0, -3.0, 4.0, -3.0], [8, -4.0, -2.0, -2.0, 1.0], [29, 1.0, 2.0, 4.0, 4.0], [36, 0.0, 4.0, 2.0, 7.0]], [[20, 1.0, -2.0, 4.0, -2.0], [8, -2.0, -1.0, 0.0, 2.0], [29, 5.0, 2.0, 8.0, 4.0], [36, 0.0, 5.0, 2.0, 8.0]]], [[], [[20, 29], [29, 36]], 3]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[21, -2.0, -5.0, 1.0, -5.0], [19, 3.0, -5.0, 5.0, -4.0], [36, -2.0, -1.0, 0.0, 0.0], [16, 5.0, -1.0, 5.0, 0.0], [1, -3.0, 3.0, -3.0, 4.0]], [[21, -1.0, -5.0, 2.0, -5.0], [19, 2.0, -6.0, 4.0, -5.0], [36, -2.0, 0.0, 0.0, 1.0], [16, 9.0, -1.0, 9.0, 0.0], [1, -3.0, 3.0, -3.0, 4.0]]], [[[19, 21]], [[16, 19]], 4]]], [[[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]], [[[[31, 1.0, 0.0, 1.0, 0.0], [38, -4.0, 1.0, -2.0, 4.0], [5, -1.0, -1.0, 0.0, -1.0], [39, 2.0, -3.0, 5.0, -3.0], [27, 3.0, 2.0, 3.0, 5.0], [4, -4.0, -1.0, -3.0, 2.0]], [[31, 1.0, 1.0, 1.0, 1.0], [38, -2.0, 1.0, 0.0, 4.0], [5, 1.0, -1.0, 2.0, -1.0], [39, 6.0, -3.0, 9.0, -3.0], [27, 0.0, 1.0, 0.0, 4.0], [4, -4.0, -1.0, -3.0, 2.0]]], [[[27, 31], [27, 38]], [[4, 38], [5, 27], [27, 31], [27, 39]], 14]], [[[[37, -1.0, -5.0, 1.0, -3.0], [39, -3.0, 0.0, -2.0, 2.0], [12, 1.0, -5.0, 4.0, -3.0], [1, -4.0, -4.0, -2.0, -2.0], [16, 1.0, -3.0, 2.0, 0.0]], [[37, 0.0, -4.0, 2.0, -2.0], [39, -3.0, -1.0, -2.0, 1.0], [12, -2.0, -4.0, 1.0, -2.0], [1, -3.0, -3.0, -1.0, -1.0], [16, 0.0, -2.0, 1.0, 1.0]]], [[[1, 12]], [], 6]], [[[[34, -5.0, 5.0, -3.0, 6.0], [25, 3.0, -4.0, 6.0, -1.0], [10, -5.0, -3.0, -4.0, -2.0], [2, -4.0, 0.0, -2.0, 0.0], [13, -3.0, 5.0, -3.0, 6.0], [3, -1.0, 2.0, 0.0, 2.0], [20, 1.0, -4.0, 1.0, -3.0]], [[34, -6.0, 4.0, -4.0, 5.0], [25, 3.0, -4.0, 6.0, -1.0], [10, -5.0, -2.0, -4.0, -1.0], [2, -3.0, -1.0, -1.0, -1.0], [13, -1.0, 4.0, -1.0, 5.0], [3, 3.0, 2.0, 4.0, 2.0], [20, 0.0, -4.0, 0.0, -3.0]]], [[], [[2, 10], [2, 34], [3, 20], [13, 34]], 10]], [[[[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]], [[[[13, -2.0, 1.0, -1.0, 2.0], [20, -5.0, 0.0, -4.0, 1.0], [37, 0.0, 5.0, 3.0, 8.0], [8, 5.0, -3.0, 5.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0]], [[13, -3.0, 1.0, -2.0, 2.0], [20, -6.0, -1.0, -5.0, 0.0], [37, 4.0, 6.0, 7.0, 9.0], [8, 5.0, -2.0, 5.0, -1.0], [2, 2.0, -1.0, 5.0, 0.0]]], [[], [], 4]], [[[[24, -1.0, -2.0, 2.0, 1.0], [30, 0.0, -3.0, 3.0, -2.0], [37, -5.0, 1.0, -5.0, 4.0], [18, 1.0, 2.0, 2.0, 4.0], [26, -3.0, -4.0, -2.0, -3.0], [29, 3.0, 2.0, 5.0, 4.0]], [[24, -2.0, -3.0, 1.0, 0.0], [30, 0.0, -2.0, 3.0, -1.0], [37, -4.0, 0.0, -4.0, 3.0], [18, 5.0, 3.0, 6.0, 5.0], [26, -3.0, -4.0, -2.0, -3.0], [29, 3.0, 2.0, 5.0, 4.0]]], [[[18, 29], [24, 26]], [[18, 24], [18, 30]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]]], [[[[[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]], [[[[25, -4.0, 3.0, -4.0, 5.0], [8, -1.0, 1.0, 2.0, 2.0], [15, -3.0, 4.0, 0.0, 4.0]], [[25, -3.0, 2.0, -3.0, 4.0], [8, -2.0, 1.0, 1.0, 2.0], [15, 1.0, 5.0, 4.0, 5.0]]], [[], [], 2]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]], [[[[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]], [[[[11, -2.0, -1.0, -2.0, 0.0], [14, 1.0, -4.0, 2.0, -3.0], [32, 5.0, 3.0, 6.0, 4.0], [6, -2.0, 5.0, 1.0, 8.0], [39, 0.0, -4.0, 1.0, -3.0], [8, -1.0, -3.0, 2.0, 0.0]], [[11, -5.0, 0.0, -5.0, 1.0], [14, 2.0, -5.0, 3.0, -4.0], [32, 5.0, 2.0, 6.0, 3.0], [6, 2.0, 4.0, 5.0, 7.0], [39, 0.0, -4.0, 1.0, -3.0], [8, 0.0, -3.0, 3.0, 0.0]]], [[], [[6, 11], [6, 39], [14, 39]], 10]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[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]], [[[[7, -2.0, -1.0, 0.0, 0.0], [10, -5.0, 1.0, -5.0, 2.0], [13, -4.0, 0.0, -1.0, 2.0], [33, 5.0, -1.0, 6.0, 0.0], [31, -4.0, -1.0, -1.0, 0.0]], [[7, -1.0, -1.0, 1.0, 0.0], [10, -3.0, 1.0, -3.0, 2.0], [13, -4.0, -1.0, -1.0, 1.0], [33, 5.0, -1.0, 6.0, 0.0], [31, -4.0, -2.0, -1.0, -1.0]]], [[[10, 13]], [], 4]]], [[[[[18, -3.0, 3.0, -1.0, 4.0], [34, 1.0, -4.0, 1.0, -2.0], [23, 4.0, -2.0, 7.0, 1.0]], [[18, -3.0, 3.0, -1.0, 4.0], [34, 3.0, -4.0, 3.0, -2.0], [23, 3.0, -2.0, 6.0, 1.0]]], [[[23, 34]], [], 1]], [[[[30, 5.0, 4.0, 7.0, 7.0], [13, -5.0, 1.0, -5.0, 2.0], [35, -3.0, 0.0, -1.0, 0.0], [14, -5.0, 3.0, -5.0, 5.0]], [[30, 2.0, 5.0, 4.0, 8.0], [13, -4.0, 0.0, -4.0, 1.0], [35, -2.0, 0.0, 0.0, 0.0], [14, -5.0, 3.0, -5.0, 5.0]]], [[], [[13, 14]], 3]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]], [[[[33, -3.0, 1.0, -1.0, 2.0], [4, 1.0, -5.0, 4.0, -4.0], [36, -4.0, 2.0, -3.0, 5.0]], [[33, -2.0, 2.0, 0.0, 3.0], [4, -2.0, -5.0, 1.0, -4.0], [36, -2.0, 1.0, -1.0, 4.0]]], [[], [], 2]], [[[[12, 2.0, -4.0, 5.0, -1.0], [4, 5.0, 0.0, 6.0, 0.0], [19, -5.0, -2.0, -4.0, -1.0], [16, -1.0, -3.0, 0.0, 0.0], [22, 5.0, 2.0, 5.0, 3.0]], [[12, 3.0, -5.0, 6.0, -2.0], [4, 5.0, 0.0, 6.0, 0.0], [19, -3.0, -2.0, -2.0, -1.0], [16, -4.0, -2.0, -3.0, 1.0], [22, 9.0, 3.0, 9.0, 4.0]]], [[[16, 19]], [[4, 22], [12, 22]], 6]], [[[[21, -1.0, 3.0, -1.0, 3.0], [13, -2.0, 1.0, 1.0, 1.0], [33, 4.0, -2.0, 7.0, 0.0], [39, 1.0, -3.0, 2.0, -3.0]], [[21, 0.0, 3.0, 0.0, 3.0], [13, -2.0, 2.0, 1.0, 2.0], [33, 6.0, -3.0, 9.0, -1.0], [39, 2.0, -4.0, 3.0, -4.0]]], [[], [[13, 39]], 1]], [[[[8, 5.0, 2.0, 6.0, 2.0], [5, -3.0, -5.0, -1.0, -4.0], [27, 0.0, 1.0, 1.0, 1.0], [16, 4.0, 2.0, 6.0, 3.0], [38, 5.0, -4.0, 8.0, -2.0], [19, -5.0, 2.0, -5.0, 5.0], [20, 1.0, 1.0, 3.0, 1.0], [31, 5.0, -1.0, 8.0, 2.0], [22, -2.0, -4.0, -2.0, -2.0]], [[8, 5.0, 3.0, 6.0, 3.0], [5, -3.0, -5.0, -1.0, -4.0], [27, 2.0, 2.0, 3.0, 2.0], [16, 1.0, 2.0, 3.0, 3.0], [38, 7.0, -3.0, 10.0, -1.0], [19, -5.0, 3.0, -5.0, 6.0], [20, 2.0, 1.0, 4.0, 1.0], [31, 9.0, 0.0, 12.0, 3.0], [22, 0.0, -3.0, 0.0, -1.0]]], [[[16, 27]], [[5, 22], [8, 16], [8, 31], [8, 38], [16, 31], [16, 38]], 15]]], [[[[[24, -3.0, 5.0, -1.0, 5.0], [29, -4.0, -1.0, -2.0, 0.0], [15, -4.0, -4.0, -4.0, -3.0], [6, 1.0, -2.0, 2.0, 1.0], [11, 4.0, 5.0, 7.0, 6.0], [13, 1.0, 5.0, 4.0, 5.0], [14, 1.0, -5.0, 4.0, -4.0], [19, 5.0, 5.0, 7.0, 6.0], [16, 5.0, 4.0, 5.0, 4.0]], [[24, -3.0, 5.0, -1.0, 5.0], [29, -5.0, -1.0, -3.0, 0.0], [15, 0.0, -4.0, 0.0, -3.0], [6, 1.0, -3.0, 2.0, 0.0], [11, 4.0, 6.0, 7.0, 7.0], [13, 2.0, 5.0, 5.0, 5.0], [14, 5.0, -5.0, 8.0, -4.0], [19, 5.0, 4.0, 7.0, 5.0], [16, 5.0, 4.0, 5.0, 4.0]]], [[[13, 19]], [[6, 14], [15, 24], [15, 29]], 16]], [[[[23, 3.0, 0.0, 6.0, 0.0], [25, -3.0, -1.0, 0.0, 2.0], [7, -3.0, 1.0, 0.0, 1.0], [21, -5.0, 4.0, -2.0, 6.0], [37, 5.0, 1.0, 5.0, 3.0], [30, -3.0, -1.0, -2.0, 1.0], [26, -3.0, 3.0, 0.0, 5.0], [5, -5.0, 3.0, -3.0, 5.0]], [[23, 2.0, -1.0, 5.0, -1.0], [25, -3.0, -1.0, 0.0, 2.0], [7, -6.0, 2.0, -3.0, 2.0], [21, -5.0, 4.0, -2.0, 6.0], [37, 5.0, 1.0, 5.0, 3.0], [30, -4.0, -1.0, -3.0, 1.0], [26, -2.0, 2.0, 1.0, 4.0], [5, -5.0, 2.0, -3.0, 4.0]]], [[], [[5, 26], [7, 26], [26, 30]], 9]], [[[[33, -1.0, -1.0, 2.0, 1.0], [8, 2.0, -3.0, 4.0, -1.0], [26, 4.0, 3.0, 6.0, 6.0], [17, -5.0, 4.0, -4.0, 6.0]], [[33, -2.0, -1.0, 1.0, 1.0], [8, 4.0, -4.0, 6.0, -2.0], [26, 1.0, 3.0, 3.0, 6.0], [17, -6.0, 4.0, -5.0, 6.0]]], [[], [[8, 26], [8, 33]], 5]], [[[[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]], [[[[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]], [[[[28, 0.0, -4.0, 2.0, -4.0], [20, 2.0, -5.0, 2.0, -3.0]], [[28, 4.0, -3.0, 6.0, -3.0], [20, 2.0, -5.0, 2.0, -3.0]]], [[], [[20, 28]], 2]], [[[[10, -5.0, -1.0, -3.0, -1.0], [17, 3.0, 4.0, 6.0, 6.0], [30, 0.0, -1.0, 0.0, -1.0], [25, 2.0, -4.0, 3.0, -4.0], [39, -2.0, 3.0, -2.0, 6.0]], [[10, -5.0, -2.0, -3.0, -2.0], [17, 3.0, 4.0, 6.0, 6.0], [30, 0.0, -1.0, 0.0, -1.0], [25, 2.0, -4.0, 3.0, -4.0], [39, -3.0, 3.0, -3.0, 6.0]]], [[], [], 1]], [[[[7, 1.0, 5.0, 1.0, 8.0], [12, -1.0, -4.0, 1.0, -1.0], [4, -3.0, -4.0, -2.0, -3.0], [26, 4.0, 5.0, 4.0, 5.0], [19, -4.0, -2.0, -4.0, 0.0], [6, 5.0, 3.0, 7.0, 3.0], [5, -1.0, 2.0, -1.0, 4.0], [30, 4.0, 0.0, 5.0, 0.0]], [[7, 1.0, 5.0, 1.0, 8.0], [12, -1.0, -4.0, 1.0, -1.0], [4, -3.0, -5.0, -2.0, -4.0], [26, 4.0, 5.0, 4.0, 5.0], [19, -4.0, -3.0, -4.0, -1.0], [6, 9.0, 2.0, 11.0, 2.0], [5, -2.0, 3.0, -2.0, 5.0], [30, 5.0, 1.0, 6.0, 1.0]]], [[], [[5, 12], [6, 30], [26, 30]], 4]]]]\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":"d1252260672f7bf0f2d2c5b05e136e778c67d0884bd93767cf8c864a589e2b84","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()\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][0]:\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 = [[[[[[38, -5.0, 2.0, -4.0, 4.0], [19, -4.0, 5.0, -4.0, 5.0], [27, -2.0, -5.0, -2.0, -3.0], [21, -2.0, -2.0, 1.0, 0.0], [12, 2.0, -5.0, 5.0, -3.0]], [[38, -1.0, 3.0, 0.0, 5.0], [19, -5.0, 5.0, -5.0, 5.0], [27, -5.0, -4.0, -5.0, -2.0], [21, 2.0, -3.0, 5.0, -1.0], [12, 6.0, -4.0, 9.0, -2.0]]], [[], [[19, 38], [21, 27], [27, 38]], 9]], [[[[22, 2.0, 1.0, 3.0, 1.0], [28, 3.0, 0.0, 4.0, 0.0], [21, -2.0, -2.0, 1.0, -1.0], [33, -1.0, 1.0, 0.0, 2.0], [11, 2.0, 5.0, 5.0, 5.0], [18, -1.0, 1.0, -1.0, 1.0]], [[22, 6.0, 1.0, 7.0, 1.0], [28, 5.0, 0.0, 6.0, 0.0], [21, 0.0, -3.0, 3.0, -2.0], [33, -4.0, 1.0, -3.0, 2.0], [11, 6.0, 5.0, 9.0, 5.0], [18, 0.0, 2.0, 0.0, 2.0]]], [[], [[18, 33], [21, 33]], 8]], [[[[36, 4.0, -3.0, 4.0, -2.0], [30, 5.0, 1.0, 5.0, 1.0]], [[36, 4.0, -3.0, 4.0, -2.0], [30, 5.0, 1.0, 5.0, 1.0]]], [[], [], 0]], [[[[3, 3.0, 0.0, 4.0, 3.0], [1, 4.0, -1.0, 6.0, 1.0]], [[3, 0.0, 1.0, 1.0, 4.0], [1, 1.0, -1.0, 3.0, 1.0]]], [[], [], 0]], [[[[5, -4.0, -1.0, -2.0, 0.0], [15, 2.0, -2.0, 5.0, -2.0]], [[5, -4.0, -1.0, -2.0, 0.0], [15, 1.0, -3.0, 4.0, -3.0]]], [[], [], 0]], [[[[20, 1.0, -3.0, 4.0, -3.0], [8, -4.0, -2.0, -2.0, 1.0], [29, 1.0, 2.0, 4.0, 4.0], [36, 0.0, 4.0, 2.0, 7.0]], [[20, 1.0, -2.0, 4.0, -2.0], [8, -2.0, -1.0, 0.0, 2.0], [29, 5.0, 2.0, 8.0, 4.0], [36, 0.0, 5.0, 2.0, 8.0]]], [[], [[20, 29], [29, 36]], 3]], [[[[32, -2.0, -1.0, -2.0, 2.0], [33, 1.0, -4.0, 2.0, -2.0], [12, 3.0, 1.0, 5.0, 2.0], [5, 1.0, 5.0, 3.0, 7.0]], [[32, -1.0, -1.0, -1.0, 2.0], [33, 1.0, -5.0, 2.0, -3.0], [12, 7.0, 1.0, 9.0, 2.0], [5, -2.0, 6.0, 0.0, 8.0]]], [[], [[5, 12], [5, 33]], 5]], [[[[21, -2.0, -5.0, 1.0, -5.0], [19, 3.0, -5.0, 5.0, -4.0], [36, -2.0, -1.0, 0.0, 0.0], [16, 5.0, -1.0, 5.0, 0.0], [1, -3.0, 3.0, -3.0, 4.0]], [[21, -1.0, -5.0, 2.0, -5.0], [19, 2.0, -6.0, 4.0, -5.0], [36, -2.0, 0.0, 0.0, 1.0], [16, 9.0, -1.0, 9.0, 0.0], [1, -3.0, 3.0, -3.0, 4.0]]], [[[19, 21]], [[16, 19]], 4]]], [[[[[6, 5.0, 4.0, 5.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -5.0, -3.0, -4.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, 0.0, 4.0, 1.0, 6.0]], [[6, 7.0, 4.0, 7.0, 7.0], [38, -3.0, 0.0, 0.0, 3.0], [18, -4.0, -3.0, -3.0, -2.0], [9, -5.0, 5.0, -5.0, 7.0], [27, -1.0, 4.0, 0.0, 6.0]]], [[], [[9, 18]], 2]], [[[[31, 1.0, 0.0, 1.0, 0.0], [38, -4.0, 1.0, -2.0, 4.0], [5, -1.0, -1.0, 0.0, -1.0], [39, 2.0, -3.0, 5.0, -3.0], [27, 3.0, 2.0, 3.0, 5.0], [4, -4.0, -1.0, -3.0, 2.0]], [[31, 1.0, 1.0, 1.0, 1.0], [38, -2.0, 1.0, 0.0, 4.0], [5, 1.0, -1.0, 2.0, -1.0], [39, 6.0, -3.0, 9.0, -3.0], [27, 0.0, 1.0, 0.0, 4.0], [4, -4.0, -1.0, -3.0, 2.0]]], [[[27, 31], [27, 38]], [[4, 38], [5, 27], [27, 31], [27, 39]], 14]], [[[[37, -1.0, -5.0, 1.0, -3.0], [39, -3.0, 0.0, -2.0, 2.0], [12, 1.0, -5.0, 4.0, -3.0], [1, -4.0, -4.0, -2.0, -2.0], [16, 1.0, -3.0, 2.0, 0.0]], [[37, 0.0, -4.0, 2.0, -2.0], [39, -3.0, -1.0, -2.0, 1.0], [12, -2.0, -4.0, 1.0, -2.0], [1, -3.0, -3.0, -1.0, -1.0], [16, 0.0, -2.0, 1.0, 1.0]]], [[[1, 12]], [], 6]], [[[[34, -5.0, 5.0, -3.0, 6.0], [25, 3.0, -4.0, 6.0, -1.0], [10, -5.0, -3.0, -4.0, -2.0], [2, -4.0, 0.0, -2.0, 0.0], [13, -3.0, 5.0, -3.0, 6.0], [3, -1.0, 2.0, 0.0, 2.0], [20, 1.0, -4.0, 1.0, -3.0]], [[34, -6.0, 4.0, -4.0, 5.0], [25, 3.0, -4.0, 6.0, -1.0], [10, -5.0, -2.0, -4.0, -1.0], [2, -3.0, -1.0, -1.0, -1.0], [13, -1.0, 4.0, -1.0, 5.0], [3, 3.0, 2.0, 4.0, 2.0], [20, 0.0, -4.0, 0.0, -3.0]]], [[], [[2, 10], [2, 34], [3, 20], [13, 34]], 10]], [[[[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]], [[[[13, -2.0, 1.0, -1.0, 2.0], [20, -5.0, 0.0, -4.0, 1.0], [37, 0.0, 5.0, 3.0, 8.0], [8, 5.0, -3.0, 5.0, -2.0], [2, 3.0, -1.0, 6.0, 0.0]], [[13, -3.0, 1.0, -2.0, 2.0], [20, -6.0, -1.0, -5.0, 0.0], [37, 4.0, 6.0, 7.0, 9.0], [8, 5.0, -2.0, 5.0, -1.0], [2, 2.0, -1.0, 5.0, 0.0]]], [[], [], 4]], [[[[24, -1.0, -2.0, 2.0, 1.0], [30, 0.0, -3.0, 3.0, -2.0], [37, -5.0, 1.0, -5.0, 4.0], [18, 1.0, 2.0, 2.0, 4.0], [26, -3.0, -4.0, -2.0, -3.0], [29, 3.0, 2.0, 5.0, 4.0]], [[24, -2.0, -3.0, 1.0, 0.0], [30, 0.0, -2.0, 3.0, -1.0], [37, -4.0, 0.0, -4.0, 3.0], [18, 5.0, 3.0, 6.0, 5.0], [26, -3.0, -4.0, -2.0, -3.0], [29, 3.0, 2.0, 5.0, 4.0]]], [[[18, 29], [24, 26]], [[18, 24], [18, 30]], 8]], [[[[25, -3.0, 5.0, -1.0, 8.0], [9, -1.0, -4.0, 0.0, -3.0], [21, 0.0, -1.0, 3.0, 0.0], [3, 0.0, 3.0, 0.0, 5.0], [4, 4.0, -2.0, 6.0, -2.0]], [[25, -3.0, 4.0, -1.0, 7.0], [9, 1.0, -4.0, 2.0, -3.0], [21, 2.0, -2.0, 5.0, -1.0], [3, 0.0, 4.0, 0.0, 6.0], [4, 4.0, -2.0, 6.0, -2.0]]], [[[4, 21]], [[3, 9], [3, 21], [9, 25]], 5]]], [[[[[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]], [[[[25, -4.0, 3.0, -4.0, 5.0], [8, -1.0, 1.0, 2.0, 2.0], [15, -3.0, 4.0, 0.0, 4.0]], [[25, -3.0, 2.0, -3.0, 4.0], [8, -2.0, 1.0, 1.0, 2.0], [15, 1.0, 5.0, 4.0, 5.0]]], [[], [], 2]], [[[[3, -5.0, -3.0, -3.0, 0.0], [10, 1.0, 3.0, 3.0, 4.0], [38, -5.0, 5.0, -4.0, 6.0]], [[3, -8.0, -2.0, -6.0, 1.0], [10, -2.0, 4.0, 0.0, 5.0], [38, -4.0, 5.0, -3.0, 6.0]]], [[], [[3, 38]], 2]], [[[[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]], [[[[11, -2.0, -1.0, -2.0, 0.0], [14, 1.0, -4.0, 2.0, -3.0], [32, 5.0, 3.0, 6.0, 4.0], [6, -2.0, 5.0, 1.0, 8.0], [39, 0.0, -4.0, 1.0, -3.0], [8, -1.0, -3.0, 2.0, 0.0]], [[11, -5.0, 0.0, -5.0, 1.0], [14, 2.0, -5.0, 3.0, -4.0], [32, 5.0, 2.0, 6.0, 3.0], [6, 2.0, 4.0, 5.0, 7.0], [39, 0.0, -4.0, 1.0, -3.0], [8, 0.0, -3.0, 3.0, 0.0]]], [[], [[6, 11], [6, 39], [14, 39]], 10]], [[[[38, -3.0, -5.0, -3.0, -4.0], [10, 4.0, 1.0, 6.0, 3.0], [15, 1.0, 0.0, 3.0, 3.0], [23, -4.0, -2.0, -1.0, 0.0], [24, -1.0, 3.0, 2.0, 4.0], [14, 3.0, -4.0, 5.0, -3.0], [26, -2.0, 3.0, 1.0, 5.0], [20, -5.0, 4.0, -4.0, 5.0]], [[38, -6.0, -6.0, -6.0, -5.0], [10, 1.0, 0.0, 3.0, 2.0], [15, 1.0, 1.0, 3.0, 4.0], [23, 0.0, -2.0, 3.0, 0.0], [24, 0.0, 2.0, 3.0, 3.0], [14, 5.0, -5.0, 7.0, -4.0], [26, -2.0, 2.0, 1.0, 4.0], [20, -3.0, 5.0, -2.0, 6.0]]], [[[10, 15], [10, 23], [10, 24], [10, 26]], [[10, 14], [14, 15], [20, 23], [20, 38], [23, 38]], 19]], [[[[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]], [[[[7, -2.0, -1.0, 0.0, 0.0], [10, -5.0, 1.0, -5.0, 2.0], [13, -4.0, 0.0, -1.0, 2.0], [33, 5.0, -1.0, 6.0, 0.0], [31, -4.0, -1.0, -1.0, 0.0]], [[7, -1.0, -1.0, 1.0, 0.0], [10, -3.0, 1.0, -3.0, 2.0], [13, -4.0, -1.0, -1.0, 1.0], [33, 5.0, -1.0, 6.0, 0.0], [31, -4.0, -2.0, -1.0, -1.0]]], [[[10, 13]], [], 4]]], [[[[[18, -3.0, 3.0, -1.0, 4.0], [34, 1.0, -4.0, 1.0, -2.0], [23, 4.0, -2.0, 7.0, 1.0]], [[18, -3.0, 3.0, -1.0, 4.0], [34, 3.0, -4.0, 3.0, -2.0], [23, 3.0, -2.0, 6.0, 1.0]]], [[[23, 34]], [], 1]], [[[[30, 5.0, 4.0, 7.0, 7.0], [13, -5.0, 1.0, -5.0, 2.0], [35, -3.0, 0.0, -1.0, 0.0], [14, -5.0, 3.0, -5.0, 5.0]], [[30, 2.0, 5.0, 4.0, 8.0], [13, -4.0, 0.0, -4.0, 1.0], [35, -2.0, 0.0, 0.0, 0.0], [14, -5.0, 3.0, -5.0, 5.0]]], [[], [[13, 14]], 3]], [[[[8, -1.0, -1.0, -1.0, -1.0], [9, 4.0, 0.0, 4.0, 3.0], [30, -3.0, 5.0, -1.0, 5.0], [32, 0.0, 2.0, 1.0, 5.0], [3, -3.0, 1.0, 0.0, 1.0], [18, -2.0, 4.0, -2.0, 7.0], [23, 5.0, 2.0, 5.0, 2.0], [39, -4.0, 4.0, -1.0, 5.0]], [[8, 0.0, -1.0, 0.0, -1.0], [9, 1.0, -1.0, 1.0, 2.0], [30, -6.0, 4.0, -4.0, 4.0], [32, -1.0, 1.0, 0.0, 4.0], [3, -3.0, 2.0, 0.0, 2.0], [18, -3.0, 4.0, -3.0, 7.0], [23, 5.0, 1.0, 5.0, 1.0], [39, -4.0, 3.0, -1.0, 4.0]]], [[[32, 39]], [[3, 30], [8, 30], [8, 39], [18, 30]], 12]], [[[[15, -4.0, 5.0, -1.0, 6.0], [21, -2.0, 1.0, -1.0, 2.0], [16, 5.0, 2.0, 8.0, 3.0], [39, 1.0, 1.0, 4.0, 1.0], [27, 1.0, -3.0, 1.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]], [[15, -4.0, 4.0, -1.0, 5.0], [21, -1.0, 1.0, 0.0, 2.0], [16, 6.0, 2.0, 9.0, 3.0], [39, 3.0, 1.0, 6.0, 1.0], [27, 3.0, -3.0, 3.0, -2.0], [12, 5.0, -5.0, 8.0, -5.0]]], [[], [], 2]], [[[[33, -3.0, 1.0, -1.0, 2.0], [4, 1.0, -5.0, 4.0, -4.0], [36, -4.0, 2.0, -3.0, 5.0]], [[33, -2.0, 2.0, 0.0, 3.0], [4, -2.0, -5.0, 1.0, -4.0], [36, -2.0, 1.0, -1.0, 4.0]]], [[], [], 2]], [[[[12, 2.0, -4.0, 5.0, -1.0], [4, 5.0, 0.0, 6.0, 0.0], [19, -5.0, -2.0, -4.0, -1.0], [16, -1.0, -3.0, 0.0, 0.0], [22, 5.0, 2.0, 5.0, 3.0]], [[12, 3.0, -5.0, 6.0, -2.0], [4, 5.0, 0.0, 6.0, 0.0], [19, -3.0, -2.0, -2.0, -1.0], [16, -4.0, -2.0, -3.0, 1.0], [22, 9.0, 3.0, 9.0, 4.0]]], [[[16, 19]], [[4, 22], [12, 22]], 6]], [[[[21, -1.0, 3.0, -1.0, 3.0], [13, -2.0, 1.0, 1.0, 1.0], [33, 4.0, -2.0, 7.0, 0.0], [39, 1.0, -3.0, 2.0, -3.0]], [[21, 0.0, 3.0, 0.0, 3.0], [13, -2.0, 2.0, 1.0, 2.0], [33, 6.0, -3.0, 9.0, -1.0], [39, 2.0, -4.0, 3.0, -4.0]]], [[], [[13, 39]], 1]], [[[[8, 5.0, 2.0, 6.0, 2.0], [5, -3.0, -5.0, -1.0, -4.0], [27, 0.0, 1.0, 1.0, 1.0], [16, 4.0, 2.0, 6.0, 3.0], [38, 5.0, -4.0, 8.0, -2.0], [19, -5.0, 2.0, -5.0, 5.0], [20, 1.0, 1.0, 3.0, 1.0], [31, 5.0, -1.0, 8.0, 2.0], [22, -2.0, -4.0, -2.0, -2.0]], [[8, 5.0, 3.0, 6.0, 3.0], [5, -3.0, -5.0, -1.0, -4.0], [27, 2.0, 2.0, 3.0, 2.0], [16, 1.0, 2.0, 3.0, 3.0], [38, 7.0, -3.0, 10.0, -1.0], [19, -5.0, 3.0, -5.0, 6.0], [20, 2.0, 1.0, 4.0, 1.0], [31, 9.0, 0.0, 12.0, 3.0], [22, 0.0, -3.0, 0.0, -1.0]]], [[[16, 27]], [[5, 22], [8, 16], [8, 31], [8, 38], [16, 31], [16, 38]], 15]]], [[[[[24, -3.0, 5.0, -1.0, 5.0], [29, -4.0, -1.0, -2.0, 0.0], [15, -4.0, -4.0, -4.0, -3.0], [6, 1.0, -2.0, 2.0, 1.0], [11, 4.0, 5.0, 7.0, 6.0], [13, 1.0, 5.0, 4.0, 5.0], [14, 1.0, -5.0, 4.0, -4.0], [19, 5.0, 5.0, 7.0, 6.0], [16, 5.0, 4.0, 5.0, 4.0]], [[24, -3.0, 5.0, -1.0, 5.0], [29, -5.0, -1.0, -3.0, 0.0], [15, 0.0, -4.0, 0.0, -3.0], [6, 1.0, -3.0, 2.0, 0.0], [11, 4.0, 6.0, 7.0, 7.0], [13, 2.0, 5.0, 5.0, 5.0], [14, 5.0, -5.0, 8.0, -4.0], [19, 5.0, 4.0, 7.0, 5.0], [16, 5.0, 4.0, 5.0, 4.0]]], [[[13, 19]], [[6, 14], [15, 24], [15, 29]], 16]], [[[[23, 3.0, 0.0, 6.0, 0.0], [25, -3.0, -1.0, 0.0, 2.0], [7, -3.0, 1.0, 0.0, 1.0], [21, -5.0, 4.0, -2.0, 6.0], [37, 5.0, 1.0, 5.0, 3.0], [30, -3.0, -1.0, -2.0, 1.0], [26, -3.0, 3.0, 0.0, 5.0], [5, -5.0, 3.0, -3.0, 5.0]], [[23, 2.0, -1.0, 5.0, -1.0], [25, -3.0, -1.0, 0.0, 2.0], [7, -6.0, 2.0, -3.0, 2.0], [21, -5.0, 4.0, -2.0, 6.0], [37, 5.0, 1.0, 5.0, 3.0], [30, -4.0, -1.0, -3.0, 1.0], [26, -2.0, 2.0, 1.0, 4.0], [5, -5.0, 2.0, -3.0, 4.0]]], [[], [[5, 26], [7, 26], [26, 30]], 9]], [[[[33, -1.0, -1.0, 2.0, 1.0], [8, 2.0, -3.0, 4.0, -1.0], [26, 4.0, 3.0, 6.0, 6.0], [17, -5.0, 4.0, -4.0, 6.0]], [[33, -2.0, -1.0, 1.0, 1.0], [8, 4.0, -4.0, 6.0, -2.0], [26, 1.0, 3.0, 3.0, 6.0], [17, -6.0, 4.0, -5.0, 6.0]]], [[], [[8, 26], [8, 33]], 5]], [[[[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]], [[[[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]], [[[[28, 0.0, -4.0, 2.0, -4.0], [20, 2.0, -5.0, 2.0, -3.0]], [[28, 4.0, -3.0, 6.0, -3.0], [20, 2.0, -5.0, 2.0, -3.0]]], [[], [[20, 28]], 2]], [[[[10, -5.0, -1.0, -3.0, -1.0], [17, 3.0, 4.0, 6.0, 6.0], [30, 0.0, -1.0, 0.0, -1.0], [25, 2.0, -4.0, 3.0, -4.0], [39, -2.0, 3.0, -2.0, 6.0]], [[10, -5.0, -2.0, -3.0, -2.0], [17, 3.0, 4.0, 6.0, 6.0], [30, 0.0, -1.0, 0.0, -1.0], [25, 2.0, -4.0, 3.0, -4.0], [39, -3.0, 3.0, -3.0, 6.0]]], [[], [], 1]], [[[[7, 1.0, 5.0, 1.0, 8.0], [12, -1.0, -4.0, 1.0, -1.0], [4, -3.0, -4.0, -2.0, -3.0], [26, 4.0, 5.0, 4.0, 5.0], [19, -4.0, -2.0, -4.0, 0.0], [6, 5.0, 3.0, 7.0, 3.0], [5, -1.0, 2.0, -1.0, 4.0], [30, 4.0, 0.0, 5.0, 0.0]], [[7, 1.0, 5.0, 1.0, 8.0], [12, -1.0, -4.0, 1.0, -1.0], [4, -3.0, -5.0, -2.0, -4.0], [26, 4.0, 5.0, 4.0, 5.0], [19, -4.0, -3.0, -4.0, -1.0], [6, 9.0, 2.0, 11.0, 2.0], [5, -2.0, 3.0, -2.0, 5.0], [30, 5.0, 1.0, 6.0, 1.0]]], [[], [[5, 12], [6, 30], [26, 30]], 4]]]]\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-endpoint-comparison-key","generated_at":"2026-09-29T14:51:01.963419+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 swap test compares coordinates only.","sha256":"0def8c20ca6a20cc846659ac48fa00e2d185d7977c4365975d2ec76138b4fda2","title":"Insertion sort ignores endpoint kind on equal coordinates · 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.111,"exit_code":1,"observations":[{"actual":[[],[[19,19],[19,27],[19,38],[21,27],[27,27],[27,38]],11],"check":"case 0","expected":[[],[[19,38],[21,27],[27,38]],9],"passed":false},{"actual":[[],[[11,28],[18,18],[18,21],[18,33],[21,33],[22,28]],12],"check":"case 1","expected":[[],[[18,33],[21,33]],8],"passed":false},{"actual":[[],[[30,30],[36,36]],2],"check":"case 2","expected":[[],[],0],"passed":false},{"actual":[[],[[1,3]],1],"check":"case 3","expected":[[],[],0],"passed":false},{"actual":[[],[],0],"check":"case 4","expected":[[],[],0],"passed":true},{"actual":[[],[[20,29],[29,36]],2],"check":"case 5","expected":[[],[[20,29],[29,36]],3],"passed":false},{"actual":[[],[[5,12],[5,33],[32,32]],6],"check":"case 6","expected":[[],[[5,12],[5,33]],5],"passed":false},{"actual":[[],[[1,1],[16,16],[16,19]],5],"check":"case 7","expected":[[[19,21]],[[16,19]],4],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], [[19, 19], [19, 27], [19, 38], [21, 27], [27, 27], [27, 38]], 11], \"expected\": [[], [[19, 38], [21, 27], [27, 38]], 9], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[], [[11, 28], [18, 18], [18, 21], [18, 33], [21, 33], [22, 28]], 12], \"expected\": [[], [[18, 33], [21, 33]], 8], \"passed\": false}, {\"check\": \"case 2\", \"actual\": [[], [[30, 30], [36, 36]], 2], \"expected\": [[], [], 0], \"passed\": false}, {\"check\": \"case 3\", \"actual\": [[], [[1, 3]], 1], \"expected\": [[], [], 0], \"passed\": false}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[], [[20, 29], [29, 36]], 2], \"expected\": [[], [[20, 29], [29, 36]], 3], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[], [[5, 12], [5, 33], [32, 32]], 6], \"expected\": [[], [[5, 12], [5, 33]], 5], \"passed\": false}, {\"check\": \"case 7\", \"actual\": [[], [[1, 1], [16, 16], [16, 19]], 5], \"expected\": [[[19, 21]], [[16, 19]], 4], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.589,"exit_code":1,"observations":[{"actual":[[],[[19,38],[21,27],[27,38]],8],"check":"case 0","expected":[[],[[19,38],[21,27],[27,38]],9],"passed":false},{"actual":[[],[[18,33],[21,33]],8],"check":"case 1","expected":[[],[[18,33],[21,33]],8],"passed":true},{"actual":[[],[],0],"check":"case 2","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 3","expected":[[],[],0],"passed":true},{"actual":[[],[],0],"check":"case 4","expected":[[],[],0],"passed":true},{"actual":[[],[[20,29],[29,36]],2],"check":"case 5","expected":[[],[[20,29],[29,36]],3],"passed":false},{"actual":[[],[[5,12],[5,33]],5],"check":"case 6","expected":[[],[[5,12],[5,33]],5],"passed":true},{"actual":[[],[[16,19]],3],"check":"case 7","expected":[[[19,21]],[[16,19]],4],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"case 0\", \"actual\": [[], [[19, 38], [21, 27], [27, 38]], 8], \"expected\": [[], [[19, 38], [21, 27], [27, 38]], 9], \"passed\": false}, {\"check\": \"case 1\", \"actual\": [[], [[18, 33], [21, 33]], 8], \"expected\": [[], [[18, 33], [21, 33]], 8], \"passed\": true}, {\"check\": \"case 2\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 3\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 4\", \"actual\": [[], [], 0], \"expected\": [[], [], 0], \"passed\": true}, {\"check\": \"case 5\", \"actual\": [[], [[20, 29], [29, 36]], 2], \"expected\": [[], [[20, 29], [29, 36]], 3], \"passed\": false}, {\"check\": \"case 6\", \"actual\": [[], [[5, 12], [5, 33]], 5], \"expected\": [[], [[5, 12], [5, 33]], 5], \"passed\": true}, {\"check\": \"case 7\", \"actual\": [[], [[16, 19]], 3], \"expected\": [[[19, 21]], [[16, 19]], 4], \"passed\": false}], \"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."}}