Цепь
Рассмотрим изотетический прямоугольник (то есть прямоугольник, стороны которого параллельны осям координат), у которого нижний левый угол находится в точке (0, 0), а правый верхний — в точке (x_max, y_max). Внутри этого прямоугольника расположены N точек: P_1 (x_1, y_1), P_2 (x_2, y_2), ..., P_N (x_N, y_N), где 0 < x_i < x_max и 0 < y_i < y_max. Рассмотрим ломаные линии SP_i1P_i2...P_ikF, которые удовлетворяют следующим условиям:
Все внутренние вершины P_ij являются некоторыми из данных точек, и количество выбранных точек может быть любым: 0 ≤ k ≤ N;
Начальная вершина S (x_S, y_S) расположена на левой стороне прямоугольника или за его пределами слева (x_S ≤ 0, 0 ≤ y_S ≤ y_max);
Конечная вершина F (x_F, y_F) расположена на правой стороне прямоугольника или за его пределами справа (x_F ≥ x_max, 0 ≤ y_F ≤ y_max).
Назовем такую ломаную постоянной длины, если и только если евклидовы длины всех её отрезков равны (|SP_i1| = |P_i1P_i2| = ... = |P_ikF|). Легко заметить, что для любого прямоугольника и любого набора данных точек существует хотя бы одна ломаная постоянной длины: это отрезок SF с координатами S(0, 0) и F(x_max, 0), который удовлетворяет всем условиям.
Ваша задача — написать программу, которая найдет ломаную постоянной длины с минимальной длиной отрезка. Заметим, что квадрат (вторая степень) минимальной длины всегда является целым числом, поэтому программа должна вывести квадрат этой длины в виде целого числа.
Входные данные
Первая строка входных данных содержит три целых числа, разделенных пробелами: x_max, y_max, N — координаты правого верхнего угла и количество данных точек. Каждая из следующих N строк содержит два целых числа, разделенных пробелами: x_i, y_i — координаты данной точки.
Ограничения: 1 ≤ N ≤ 1000; 5 ≤ x_max, y_max ≤ 32000; для всех 1 ≤ i ≤ N, 0 < x_i < x_max, 0 < y_i < y_max.
Выходные данные
Ваша программа должна вывести ровно одно целое число: квадрат минимально возможной длины отрезка среди ломаных постоянной длины.
Примечание: Мы можем построить некоторые ломаные постоянной длины с определенной длиной (например: (–2, 6), (2, 8), (6, 6), (6+, 6)), но не можем построить ни одной ломаной постоянной длины для меньших длин.