| Codeforces Round 340 (Div. 2) |
|---|
| Закончено |
На клумбе много цветов, и для их поливки используют два фонтанчика. Регулируя напор, можно установить любые значения радиусов 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. Обратите внимание, что в данной задаче оптимальный ответ всегда выражается целым числом.
2 -1 0 5 3
0 2
5 2
6
4 0 0 5 0
9 4
8 3
-1 0
1 4
33
Первый пример (r12 = 5, r22 = 1): 
Второй пример (r12 = 1, r22 = 32): 
