1. Идея

Нужно найти длину стороны квадрата по его площади a.

Если сторона равна x, то площадь равна x * x. Значит, требуется найти такое число x, что:

• x * x = a

То есть фактически нужно вычислить квадратный корень из a.

По условию задачу нужно решать именно вещественным двоичным поиском. Будем искать ответ на некотором отрезке [l, r], постепенно сужая его.

2. Наблюдения

1. Искомая длина стороны не может быть отрицательной, значит можно искать ответ среди неотрицательных чисел.

2. Если a = 0, то ответ сразу равен 0.

3. Для a > 0 можно взять начальный отрезок:

   • l = 0
   • r = max(1, a)

   Почему этого достаточно:

   • если 0 < a < 1, корень мог бы быть больше a, но в нашей задаче a — целое число, так что такого случая нет;
   • если a >= 1, то sqrt(a) <= a, значит корень точно лежит в [0, a];
   • для a = 1 отрезок [0, 1] тоже подходит.

4. Проверка середины m очень проста:

   • если m * m < a, значит m слишком маленькое, нужно двигать левую границу;
   • иначе m уже не меньше корня, значит нужно двигать правую границу.

5. Так как работаем с вещественными числами, удобно не ждать точного совпадения, а выполнить фиксированное число итераций.
   В эталонном решении используется 100 шагов — этого более чем достаточно для точности 10^(-6).

3. Алгоритм

1. Считать число a.
2. Если a == 0, вывести 0.0000000000.
3. Иначе:
   • установить l = 0.0
   • установить r = max(1, a) как вещественное число
4. Повторить 100 раз:
   • m = (l + r) / 2
   • если m * m < a, то l = m
   • иначе r = m
5. После цикла вывести (l + r) / 2 с достаточным количеством знаков после запятой.

4. Почему это работает

Двоичный поиск поддерживает такой инвариант:

• истинный ответ всегда находится внутри отрезка [l, r].

Сначала это верно:

• l = 0
• r = max(1, a)
• корень из a действительно лежит внутри этого отрезка.

Дальше на каждом шаге берём середину m.

Случай 1: m * m < a

Тогда m меньше настоящего корня, потому что квадрат числа растёт при росте неотрицательного числа.
Значит ответ лежит правее m, и можно заменить l на m.

Случай 2: m * m >= a

Тогда m не меньше настоящего корня. Значит ответ лежит не правее m, и можно заменить r на m.

В обоих случаях новый отрезок всё ещё содержит ответ, но становится в 2 раза короче.

После 100 шагов длина отрезка становится очень маленькой, поэтому любое число внутри него, например (l + r) / 2, будет приближать корень с нужной точностью.

5. Сложность

На каждом шаге делается константное число операций, а шагов ровно 100.

• Время: O(100), то есть фактически O(1)
• Память: O(1)

6. Код на C++17

#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

int main() {
    long long a;
    cin >> a;

    if (a == 0) {
        cout << fixed << setprecision(10) << 0.0 << "\n";
        return 0;
    }

    double l = 0.0;
    double r = (double)max(1LL, a);

    for (int i = 0; i < 100; i++) {
        double m = (l + r) / 2.0;
        if (m * m < (double)a) {
            l = m;
        } else {
            r = m;
        }
    }

    cout << fixed << setprecision(10) << (l + r) / 2.0 << "\n";
    return 0;
}

7. Код на Python 3

a = int(input())

if a == 0:
    print("0.0000000000")
else:
    l = 0.0
    r = float(max(1, a))

    for _ in range(100):
        m = (l + r) / 2.0
        if m * m < a:
            l = m
        else:
            r = m

    print(f"{(l + r) / 2.0:.10f}")