Problem p03576 (python)

Fixed submission:
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)

Buggy submission (verdict: Runtime Error):
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)
if N == 2:
    print(area(a,b))
    exit()

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)

Buggy submission (verdict: Runtime Error):
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)
if N == 2:
    print(area(a,b))
    exit()

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
mn_x, mn_y, mx_x, mx_y = inf, inf, 0, 0
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
    mn_x, mn_y, mx_x, mx_y = min(mn_x, a), min(mn_y, b), max(mx_x, a), max(mx_y, b)

if N == 2:
    print(area(a,b))
    exit()
center = [(mx_x - mn_x) // 2, (mx_y - mn_y) // 2]
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j]) + dist(A[j], center)
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    # print(idx, mn_lst, graph[3][3])
    tmp_lst = [[graph[idx][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))
# for i in range(N):
#     print(graph[i])
# print(a,b, cands)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
mn_x, mn_y, mx_x, mx_y = inf, inf, 0, 0
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
    mn_x, mn_y, mx_x, mx_y = min(mn_x, a), min(mn_y, b), max(mx_x, a), max(mx_y, b)

if N == 2:
    print(area(a,b))
    exit()
center = [(mx_x - mn_x) / 2, (mx_y - mn_y) / 2]
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j]) + dist(A[j], center)
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    # print(idx, mn_lst, graph[3][3])
    tmp_lst = [[graph[idx][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))
# for i in range(N):
#     print(graph[i])
# print(a,b, cands)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b), mn_lst)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
if N == 2:
    print(area(a,b))
    exit()
    
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]
print(mn_dict, mn_dist)

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
print(cands)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b), mn_lst)

Buggy submission (verdict: Runtime Error):
from heapq import heappop, heappush
N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])

ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)>>1
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j])
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    tmp_lst = [[graph[mn_lst[idx]][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))