Problems
Bog (RU)
Bog (RU)
Болото имеет форму прямоугольника со сторонами, параллельными осям координат, два противоположных угла болота имеют координаты (\textbf{0},\textbf{0}) и (\textbf{W},\textbf{H}), где \textbf{W} и \textbf{H} - целые положительные числа. В болоте есть \textbf{N} кочек с целочисленными координатами. Девочка Валя подошла к левому краю болота. Валя может перейти через болото прыгнув с левого берега на какую-то кочку, затем перепрыгивая с кочки на кочку и, наконец, прыгнув с кочки на правый берег. К сожалению девочка Валя страдает синдромом навязчивых состояний, поэтому прыгать она может только на одну и ту же длину. Значит расстояние между соседними кочками в ее пути должно равняться некоторому фиксированному числу \textbf{L}, а расстояние от левого берега до первой кочки и от последней кочки до правого берега не должно превышать \textbf{L}. Определите наименьшую длину прыжка \textbf{L}, которая позволит девочке Вале перейти болото.
\textbf{Входные данные.} В первой строке находятся три целых числа: \textbf{W}, \textbf{H} и \textbf{N}. В последующих \textbf{N} строках находятся пары чисел \textbf{X}, \textbf{Y} - координаты кочек. \textbf{0} < \textbf{W}, \textbf{H} <= \textbf{100}; 0 < \textbf{N} <= \textbf{1000}. Выходные данные. Целое число \textbf{L^2}, где \textbf{L} - искомая длина.
Input example #1
7 4 4 3 1 1 3 5 3 5 1
Output example #1
8