← 返回题目列表

Codeforces · 617/C

C. 浇花

中文机器翻译题面 查看原题

花坛里有很多花和两个喷泉。

您可以调整水压并设置任意值 r1(r1 ≥ 0) 和 r2(r2 ≥ 0),分别给出水从第一个和第二个喷泉扩散的距离。你必须设置这样的r1和r2,让所有的花都被浇水,也就是说,对于每朵花,花到第一个喷泉的距离不超过r1,或者到第二个喷泉的距离不超过r2。如果一些花可以用两个喷泉浇水就可以了。

您需要减少所需的水量,即设置 r1 和 r2,使所有花都浇水,并且 r12 + r22 是可能的最小值。找到这个最小值。

输入

输入的第一行包含整数 n, x1, y1, x2, y2 (1 ≤ n ≤ 2000, - 107 ≤ x1, y1, x2, y2 ≤ 107) - 花的数量,第一个和第二个喷泉的坐标。

接下来是 n 行。这些行的第 i 行包含整数 xi 和 yi (- 107 ≤ xi, yi ≤ 107)——第 i 朵花的坐标。

保证输入中的所有 n + 2 个点都是不同的。

输出

打印最小可能值 r12 + r22。请注意,在此问题中,最佳答案始终是整数。

示例

输入 #1

2 -1 0 5 3
0 2
5 2

输出 #1

6

输入 #2

4 0 0 5 0
9 4
8 3
-1 0
1 4

输出 #2

33

注意

第一个样本为 (r12 = 5, r22 = 1): 第二个样本为 (r12 = 1, r22 = 32):