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

Болото

Болото

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

Болото має форму прямокутника зі сторонами, паралельними осям координат, два пролежних кути болота мають координати (0,0) і (W,H), де W и H - цілі додатні числа. В болоті є N купин з цілочисельними координатами. Дівчинка Валя підійшла до лівого краю болота. Валя може перейти через болото стрибнувши з лівого берега на якусь купину, потім перестрибуючи з купини на купину і, нарешті, стрибнувши з купини на правий берег. На жаль дівчинка Валя страдає синдромом нав'язливих станів, тому стрибати вона може лише на одну і ту ж довжину. Значить відстань між сусідніми купинами на її шляху повинна дорівнювати деякому фікованому числу L, а відстань від лівого берега до першої купини і від останньої купини до правого берега не повинна перевищувати L. Визначіть найменшу довжина стрибка L, яка дозволить дівчинці Валі перейти болото.

Вхідні дані. У першому рядку містяться три цілих числа: W, H і N. У наступних N рядках містяться пари чисел X, Y - координати купин. 0 < W, H <= 100; 0 < N <= 1000. Вихідні дані. Ціле число L^2, де L - шукана довжина.

Приклад

Вхідні дані #1
7 4 4
3 1
1 3
5 3
5 1
Вихідні дані #1
8