結果

問題 No.735 接線
コンテスト
ユーザー yukicoder
提出日時 2026-10-14 11:36:16
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
+ 19µs
コード長 2,333 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,203 ms
コンパイル使用メモリ 154,864 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-10-14 11:36:23
合計ジャッジ時間 4,585 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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 <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <iostream>

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;
}
0