Розглянемо геометричний зміст функції. Позначимо , B = (c, d) та P = (x, y). Тоді
тобто це сума відстаней від точки до двох фіксованих точок і .
За нерівністю трикутника для будь-якої точки виконується
причому рівність досягається тоді й лише тоді, коли лежить на відрізку . Така точка завжди існує, отже мінімум досягається і дорівнює саме .
Тому відповідь на кожен запит — це відстань між точками і :
Ніякого потрійного пошуку чи іншої оптимізації не потрібно: кожен запит обробляється за , загальна складність — .
Дві технічні деталі. По-перше, різниці координат сягають 10^6, тому квадрати треба рахувати у 64-бітному типі, інакше добуток переповниться. По-друге, відповідь дійсна, тому виводьте її з достатньою кількістю знаків після крапки — допускається похибка до 10^{-4}.