分享一个0-1背包的思路,O(n^2 2^n)。
def get_inputs(fun=int):
return list(map(fun, input().split()))
T = get_inputs()[0]
for _ in range(T):
N, M = get_inputs()
arr = []
for _ in range(N):
x, y = get_inputs(float)
arr.append((x,y))
if N <= 1:
print(1)
continue
eqs = set()
for i in range(N):
for j in range(i+1, N):
x1, y1 = arr[i]
x2, y2 = arr[j]
a11, a12, b1 = x1 ** 2, x1, y1
a21, a22, b2 = x2 ** 2, x2, y2
f = a11 * a22 - a12 * a21
if f == 0:
continue
a, b = (b1 * a22 - b2 * a12) / f, (b2 * a11 - b1 * a21) / f
if a < 0:
eqs.add((a,b))
eqs = list(eqs)
infos = []
max_by = 0
lefts = set(range(len(arr)))
for (a,b) in eqs:
tmp = 0
for i, (x, y) in enumerate(arr):
if abs(a * x ** 2 + b * x - y) < 1e-6:
max_by = max_by | (1 << i)
tmp = tmp | (1 << i)
if i in lefts:
lefts.remove(i)
infos.append(tmp)
F = [float('inf')] * len(eqs)
F = [[float('inf')] * (1 << N),[float('inf')] * (1 << N)]
F[0][0] = 0
F[1][0] = 0
for i, x in enumerate(infos):
for k in range(1 << N):
F[i&1][k] = F[1-(i&1)][k]
for k in range(1 << N):
F[i&1][k|x] = min(F[i&1][k|x], F[1-(i&1)][k] + 1)
M = (1 << N) - 1
r1 = F[(len(infos) - 1) & 1][max_by]
r2 = len(lefts)
print(r1+r2)