// No.735 を浮動小数を使わずに解く。答えは小数点以下 12 桁まで正確(四捨五入)。 // // r, d は小数第 6 位まで与えられるので、10^6 倍した整数 R, D として読む(double で読むと、 // 524288.000001 のような値は読んだ時点で 10^-6 の精度を失う)。 // 答え sqrt(d^2 - r^2) = sqrt((D-R)(D+R)) / 10^6。小数点以下 12 桁の整数 Y = 答え * 10^12 は // Y = sqrt((D-R)(D+R) * 10^12) // で、(D-R)(D+R) < 2*10^24 なので中身は 2*10^36 未満となり __int128(約 1.7*10^38 まで)に収まる。 // 平方根は整数で求め、四捨五入する。 #include #include #include #include #include typedef __int128 i128; typedef unsigned __int128 u128; // "123.456789" や "5" を 10^6 倍した整数にする(小数部が 6 桁未満なら 0 で埋める) static long long readFixed6(const std::string& s) { long long ip = 0, fp = 0; size_t i = 0; for (; i < s.size() && s[i] != '.'; i++) ip = ip * 10 + (s[i] - '0'); int digits = 0; if (i < s.size() && s[i] == '.') { for (i++; i < s.size() && digits < 6; i++, digits++) fp = fp * 10 + (s[i] - '0'); } for (; digits < 6; digits++) fp *= 10; return ip * 1000000LL + fp; } // floor(sqrt(n)) static u128 isqrt(u128 n) { if (n == 0) return 0; // 初期値は 2^(ビット数/2 の切り上げ) で、必ず答え以上から始める int bits = 0; for (u128 t = n; t; t >>= 1) bits++; u128 x = (u128)1 << ((bits + 1) / 2); while (true) { u128 y = (x + n / x) / 2; if (y >= x) return x; x = y; } } int main() { std::string rs, ds; std::cin >> rs >> ds; long long R = readFixed6(rs), D = readFixed6(ds); u128 v = (u128)(D - R) * (u128)(D + R); // 単位 10^-12 u128 n = v * (u128)1000000000000ULL; // 平方根の単位が 10^-12 になるように u128 y = isqrt(n); // 四捨五入: (y + 0.5)^2 <= n なら切り上げ。両辺 4 倍して整数で比べる if ((2 * y + 1) * (2 * y + 1) <= 4 * n) y++; unsigned long long ip = (unsigned long long)(y / (u128)1000000000000ULL); unsigned long long fp = (unsigned long long)(y % (u128)1000000000000ULL); std::printf("%llu.%012llu\n", ip, fp); return 0; }