import os

def squared_distance(biker, bike): return (biker[0] - bike[0]) ** 2 + (biker[1] - bike[1]) ** 2

def bikeRacers(bikers, bikes, k): # Generate all unique squared distances between bikers and bikes distances = [] for biker in bikers: for bike in bikes: dist = squared_distance(biker, bike) distances.append(dist) distances = sorted(set(distances)) # Unique sorted distances

# Binary search on the possible distances
left, right = 0, len(distances) - 1
while left < right:
    mid = (left + right) // 2
    max_dist = distances[mid]

    # Check if we can match `k` bikers with `k` bikes within this max_dist
    if can_match_with_distance(bikers, bikes, k, max_dist):
        right = mid  # Try a smaller maximum distance
    else:
        left = mid + 1  # Try a larger maximum distance

return distances[left]

def can_match_with_distance(bikers, bikes, k, max_dist): n, m = len(bikers), len(bikes) graph = [[] for _ in range(n)]

# Create bipartite graph edges within max_dist
for i in range(n):
    for j in range(m):
        if squared_distance(bikers[i], bikes[j]) <= max_dist:
            graph[i].append(j)

# Bipartite matching using DFS
matched_bikes = [-1] * m

def dfs(biker, visited):
    for bike in graph[biker]:
        if not visited[bike]:
            visited[bike] = True
            if matched_bikes[bike] == -1 or dfs(matched_bikes[bike], visited):
                matched_bikes[bike] = biker
                return True
    return False

match_count = 0
for biker in range(n):
    visited = [False] * m
    if dfs(biker, visited):
        match_count += 1
    if match_count >= k:
        return True

return False

Input Handling

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
k = int(first_multiple_input[2])

bikers = [tuple(map(int, input().rstrip().split())) for _ in range(n)]
bikes = [tuple(map(int, input().rstrip().split())) for _ in range(m)]

result = bikeRacers(bikers, bikes, k)
fptr.write(str(result) + '\n')
fptr.close()