# wifi ## 题目描述 现在有一种神奇的工具，所有和这种工具距离不超过破解半径的路由器密码都会被其破解，当破解半径为0的时候，它恰好就可以破解和它在同一个位置的路由器，但是该工具每天只能使用同一个破解半径，而每天需要付出的费用是所有工具的破解半径的平方和。现在只有两个工具可供使用，现在要求能够破解所有的路由器密码，请计算当天的最小费用 ## 输入格式 第一行包含 4 个整数 x1、y1、x2、y2，表示这两个工具的坐标分别为(x1, y1)、(x2, y2)。 第二行包含 1 个整数 N，表示有 N 个路由器。接下来 N 行，每行两个整数 x、y，中间用一个空格隔开，表示一个路由器的坐标(x, y)。不同理由起的坐标可能相同。 ## 输出格式 输出当天的最小使用费用 ## 样例 #1 ### 样例输入 #1 ``` 0 0 10 0 2 -3 3 10 0 ``` ### 样例输出 #1 ``` 18 ``` ## 样例 #2 ### 样例输入 #2 ``` 0 0 6 0 5 -4 -2 -2 3 4 0 6 -2 9 1 ``` ### 样例输出 #2 ``` 30 ``` ## 提示 对于 10%的数据，N = 1 对于 20%的数据，1 ≤ N ≤ 2 对于 40%的数据，1 ≤ N ≤ 100 对于 70%的数据，1 ≤ N ≤ 1000 对于 100%的数据，1 ≤ N ≤ 100000，且所有坐标分量的绝对值都不超过 1000。

对于这个问题，我们可以使用动态规划来解决。

首先，我们需要计算每个路由器与两个工具之间的距离。然后，我们可以创建一个二维数组 dp，其中 dp[i][j] 表示使用工具 1 在第 i 个路由器，工具 2 在第 j 个路由器的情况下的最小费用。

然后，我们可以使用递推关系来计算 dp[i][j]。对于每个 dp[i][j]，我们有两种情况：
1. 工具 1 在第 i-1 个路由器，工具 2 在第 j 个路由器。此时，dp[i][j] = dp[i-1][j] + dis(i-1, i) ^ 2，其中 dis(i-1, i) 表示第 i-1 个路由器与第 i 个路由器之间的距离。
2. 工具 1 在第 i 个路由器，工具 2 在第 j-1 个路由器。此时，dp[i][j] = dp[i][j-1] + dis(j-1, j) ^ 2，其中 dis(j-1, j) 表示第 j-1 个路由器与第 j 个路由器之间的距离。

最终的最小费用就是 dp[N][N]，其中 N 表示路由器的数量。

下面是使用 Python 编写的实现代码：

import sys

# 计算两点之间的距离
def distance(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def min_cost(x1, y1, x2, y2, routers):
    n = len(routers)
    dp = [[sys.maxsize] * (n+1) for _ in range(n+1)]
    dp[0][0] = 0

    for i in range(1, n+1):
        for j in range(i+1):
            if j < i:
                dp[i][j] = dp[i-1][j] + distance(x1, y1, routers[i-1][0], routers[i-1][1]) ** 2
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + distance(x2, y2, routers[j-1][0], routers[j-1][1]) ** 2)

    return dp[n][n]

# 读取输入
x1, y1, x2, y2 = map(int, input().split())
n = int(input())
routers = []
for _ in range(n):
    x, y = map(int, input().split())
    routers.append((x, y))

# 计算最小费用
result = min_cost(x1, y1, x2, y2, routers)
print(result)

希望可以帮助到你！如果有任何疑问，请随时提问。