ES1961 construction reproduced exactly (metric 1.0 = records matched, none beaten); deterministic, exact-integer

-"""Baseline: random greedy. Draws random integer points and keeps each one that leaves the set in
-general position and free of convex k-gons. Lands well short of the 2^(k-2) records; the
-Erdos-Szekeres cup/cap construction described in program.md reaches all of them."""
+"""Erdos-Szekeres (1961) cup/cap construction for k = 6..10, exact integer coordinates.
 
+build(k, time_budget, seed) returns 2^(k-2) points in general position with no convex k-gon
+(recursively placed cup/cap blocks f(a,b): f(2,b)=f(a,2)= one point, f(a,b) = f(a,b-1) on the
+left + f(a-1,b) right and above with exact separation conditions; blocks S_i = f(i+2, k-i) placed
+left to right, each far right and below everything before it). Deterministic; seed unused.
+"""
 import functools
-import random
-import time
 
+_f_memo = {}
 
-def largest_convex_polygon(pts, stop_at):
-    """Exact: size of the largest subset in convex position (early exit at stop_at)."""
-    P = sorted(pts, key=lambda p: (p[1], p[0]))
-    n = len(P)
-    best_overall = min(3, n)
 
-    def cmp(a, b):
-        c = a[0] * b[1] - a[1] * b[0]
-        return -1 if c > 0 else (1 if c < 0 else 0)
+def _merge_right_up(L, R):
+    if not L or not R:
+        return list(L) + list(R)
+    X0 = max(p[0] for p in L) - min(p[0] for p in R) + 1
+    Y0 = max(p[1] for p in L) - min(p[1] for p in R) + 1
+    for l1 in L:
+        for l2 in L:
+            dlx = l2[0] - l1[0]
+            if dlx <= 0:
+                continue
+            dly = l2[1] - l1[1]
+            for r in R:
+                T = dly * X0 - (dlx * (r[1] - l1[1]) - dly * (r[0] - l1[0]))
+                yc = T // dlx + 1
+                if yc > Y0:
+                    Y0 = yc
+    for r1 in R:
+        for r2 in R:
+            drx = r2[0] - r1[0]
+            if drx <= 0:
+                continue
+            dry = r2[1] - r1[1]
+            for l in L:
+                T = (drx * (l[1] - r1[1]) - dry * (l[0] - r1[0])) + dry * X0
+                yc = T // drx + 1
+                if yc > Y0:
+                    Y0 = yc
+    return list(L) + [(X0 + x, Y0 + y) for (x, y) in R]
 
-    for i in range(n):
-        px, py = P[i]
-        Q = [(x - px, y - py) for (x, y) in P[i + 1:]]
-        M = len(Q)
-        if M < 2 or M + 1 < stop_at:
-            continue
-        Q.sort(key=functools.cmp_to_key(cmp))
-        L = [[0] * M for _ in range(M)]
-        for b in range(M):
-            bx, by = Q[b]
-            for a in range(b):
-                ax, ay = Q[a]
-                dx, dy = bx - ax, by - ay
-                La = L[a]
-                best = 3
-                for c in range(a):
-                    lc = La[c]
-                    if lc + 1 > best and (ax - Q[c][0]) * dy - (ay - Q[c][1]) * dx > 0:
-                        best = lc + 1
-                L[b][a] = best
-                if best > best_overall and dy * bx - dx * by > 0:
-                    best_overall = best
-                    if best_overall >= stop_at:
-                        return best_overall
-    return best_overall
 
+def _merge_right_down(L, R):
+    if not L or not R:
+        return list(L) + list(R)
+    X0 = max(p[0] for p in L) - min(p[0] for p in R) + 1
+    Y0 = min(p[1] for p in L) - max(p[1] for p in R) - 1
+    for l1 in L:
+        for l2 in L:
+            dlx = l2[0] - l1[0]
+            if dlx <= 0:
+                continue
+            dly = l2[1] - l1[1]
+            for r in R:
+                T = dly * X0 - (dlx * (r[1] - l1[1]) - dly * (r[0] - l1[0]))
+                yc = -((-T) // dlx) - 1
+                if yc < Y0:
+                    Y0 = yc
+    for r1 in R:
+        for r2 in R:
+            drx = r2[0] - r1[0]
+            if drx <= 0:
+                continue
+            dry = r2[1] - r1[1]
+            for l in L:
+                T = (drx * (l[1] - r1[1]) - dry * (l[0] - r1[0])) + dry * X0
+                yc = -((-T) // drx) - 1
+                if yc < Y0:
+                    Y0 = yc
+    return list(L) + [(X0 + x, Y0 + y) for (x, y) in R]
 
-def keeps_general_position(pts, q):
-    qx, qy = q
-    for i in range(len(pts)):
-        ax, ay = pts[i]
-        dx, dy = qx - ax, qy - ay
-        for j in range(i + 1, len(pts)):
-            if dx * (pts[j][1] - ay) - dy * (pts[j][0] - ax) == 0:
-                return False
-    return True
 
+def _f_block(a, b):
+    if a < 2 or b < 2:
+        raise ValueError("a,b >= 2")
+    if a == 2 or b == 2:
+        return [(0, 0)]
+    key = (a, b)
+    if key in _f_memo:
+        return _f_memo[key]
+    out = _merge_right_up(_f_block(a, b - 1), _f_block(a - 1, b))
+    _f_memo[key] = out
+    return out
 
-def build(k: int, time_budget: float, seed: int) -> list[tuple[int, int]]:
-    rnd = random.Random(seed)
-    t0 = time.perf_counter()
-    pts: list[tuple[int, int]] = []
-    for _ in range(300):
-        if time.perf_counter() - t0 > 0.8 * time_budget:
-            break
-        q = (rnd.randrange(1000), rnd.randrange(1000))
-        if q in pts or not keeps_general_position(pts, q):
-            continue
-        cand = pts + [q]
-        if len(cand) >= k and largest_convex_polygon(cand, k) >= k:
-            continue
-        pts = cand
-    return pts
 
+def _es_construction(k):
+    S = list(_f_block(2, k))
+    for i in range(1, k - 1):
+        S = _merge_right_down(S, _f_block(i + 2, k - i))
+    return S
+
+
+def build(k: int, time_budget: float, seed: int):
+    if k < 4 or k > 10:
+        return [(10 ** 6 + i, 10 ** 12 + i * i) for i in range(max(8, k))]
+    return _es_construction(k)
+