Прямокутник і точки
Обмеження: 2 сек., 512 МіБ
Дано прямокутник розміром n×m на координатній площині. Лівий нижній кут прямокутника знаходиться в точці (0,0), а правий верхній — в точці (n,m). Всередині цього прямокутника розташовано k точок.
Потрібно перемістити прямокутник (не обертаючи і не змінюючи його розмірів) так, щоб всі k точок опинилися на межах або поза межами прямокутника. Переміщення може здійснюватися у будь-якому напрямку на площині. Відстань, на яку перемістили прямокутник, визначається як евклідова відстань між початковим положенням лівого нижнього кута (0,0) та новим положенням цього кута (dx,dy).
Ваше завдання — знайти мінімальну відстань, на яку потрібно перемістити прямокутник, щоб кожна з k точок опинилася на межах або поза межами прямокутника.
Вхідні дані
Перший рядок містить три цілі числа n, m, k — розміри прямокутника та кількість точок всередині нього.
Наступні k рядків містять по два цілі числа xi, yi — координати точок, розташованих всередині прямокутника.
Вихідні дані
Виведіть одне число — мінімальну евклідову відстань, на яку потрібно перемістити прямокутник, щоб усі k точок опинилися поза його межами.
Обмеження
2≤n,m≤109,
1≤k≤2⋅105,
1≤xi<n, 1≤yi<m.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
10 10 3 1 4 2 2 3 1 | 2.2360679775 |
Примітки
Відстань між двома точками (x1,y1) та (x2,y2) обчислюється за формулою √(x2−x1)2+(y2−y1)2.
Червоним кольором показано прямокутник після переміщення, його лівий нижній кут знаходиться в точці (2,1). Тому відстань на яку було пересунуто рахуємо як dist((0,0), (2,1)) = √(2−0)2+(1−0)2=2.2360679775.