eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Болото

Болото

Болото має форму прямокутника зі сторонами, паралельними осям координат, два пролежних кути болота мають координати (\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{Вихідні дані.} Ціле число \textbf{L^2}, де \textbf{L} - шукана довжина.
Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
7 4 4
3 1
1 3
5 3
5 1
Вихідні дані #1
8