Знову функція?#32

Знову функція? (Editorial)

Розглянемо геометричний зміст функції. Позначимо , B = (c, d) та P = (x, y). Тоді

f(x, y) = |PA| + |PB|,

тобто це сума відстаней від точки до двох фіксованих точок і .

За нерівністю трикутника для будь-якої точки виконується

|PA| + |PB| \ge |AB|,

причому рівність досягається тоді й лише тоді, коли лежить на відрізку . Така точка завжди існує, отже мінімум досягається і дорівнює саме .

Тому відповідь на кожен запит — це відстань між точками і :

\sqrt{(a-c)^2 + (b-d)^2}.

Ніякого потрійного пошуку чи іншої оптимізації не потрібно: кожен запит обробляється за , загальна складність — .

Дві технічні деталі. По-перше, різниці координат сягають 10^6, тому квадрати треба рахувати у 64-бітному типі, інакше добуток переповниться. По-друге, відповідь дійсна, тому виводьте її з достатньою кількістю знаків після крапки — допускається похибка до 10^{-4}.