結果

問題 No.1944 ∞
ユーザー qwewe
提出日時 2025-05-14 13:09:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 2,000 ms
コード長 5,250 bytes
コンパイル時間 706 ms
コンパイル使用メモリ 75,696 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-06-20 02:56:06
合計ジャッジ時間 1,941 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric> // Not used, but included for completeness
#include <algorithm> // Used for std::reverse in operator<< (if enabled)
#include <string> // Used for std::string in operator<< (if enabled)

// Check if the compiler supports __int128_t (typically GCC and Clang)
#if defined(__GNUC__) || defined(__clang__)
#define HAS_INT128 
#endif

/* 
// Optional: Define output stream operator for __int128_t for debugging. 
// Can be useful during development but not required for the solution logic.
#ifdef HAS_INT128
#include <ostream> // Required for std::ostream

std::ostream& operator<<(std::ostream& os, __int128_t val) {
    if (val == 0) return os << "0"; // Handle 0 case
    std::string s = "";
    bool neg = val < 0;
    // Use unsigned type to handle the absolute value correctly, especially for the minimum negative value.
    __uint128_t uval = val; 
    if (neg) uval = -val; 

    // Convert the absolute value to string digit by digit
    while (uval > 0) {
        s += (char)('0' + uval % 10);
        uval /= 10;
    }
    if (neg) s += '-'; // Prepend '-' if negative
    std::reverse(s.begin(), s.end()); // Reverse the string since digits were extracted in reverse order
    return os << s;
}
#endif 
*/


int main() {
    // Optimize standard Input/Output operations for potentially large inputs.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of circles
    long long X_ll, Y_ll; // Coordinates of the target point. Use long long since values can be up to 10^9.
    std::cin >> N >> X_ll >> Y_ll;

    std::vector<long long> R(N); // Vector to store the radii of the N circles.
    long long min_R = -1; // Variable to store the minimum radius found. Initialized to -1 as a sentinel value.
    
    #ifdef HAS_INT128
        // Use 128-bit integer type for the sum of radii. While the sum itself might fit in long long (up to 2e10),
        // intermediate calculations like 2*sum_R and especially K*K might exceed long long's capacity.
        __int128_t sum_R = 0; 
    #else
        // If __int128_t is not available, this problem cannot be reliably solved using standard C++ types due to potential overflow.
        // Throw a compile-time error in such cases.
        #error "__int128_t is required but not supported by the compiler."
        return 1; // Indicate an error exit status.
    #endif

    // Read the radii from input.
    // Calculate the sum of all radii.
    // Find the minimum radius among all circles.
    for (int i = 0; i < N; ++i) {
        std::cin >> R[i];
        sum_R += R[i]; 
        // Update min_R if the current radius R[i] is smaller than the current min_R,
        // or if min_R is still the initial sentinel value (-1).
        if (min_R == -1 || R[i] < min_R) {
            min_R = R[i];
        }
    }

    #ifdef HAS_INT128
        // Calculate the squared distance of the target point (X,Y) from the origin (0,0).
        // Use __int128_t cast before multiplication to ensure intermediate products (X_ll*X_ll or Y_ll*Y_ll) 
        // do not overflow if they exceed the maximum value of long long (approx 9e18).
        // The sum X^2 + Y^2 could reach up to 2*10^18, which still fits in long long, but using __int128_t provides safety.
        __int128_t target_dist_sq = (__int128_t)X_ll * X_ll + (__int128_t)Y_ll * Y_ll;
        
        // Handle the special case where there is only one circle (N=1).
        if (N == 1) {
            // For N=1, the single circle must be placed centered at the origin.
            // For it to be tangent to the point (X,Y), the distance from the origin to (X,Y) must be exactly equal to the circle's radius R[0].
            // We compare the squared distance to the squared radius to avoid floating point calculations.
            __int128_t R1_sq = (__int128_t)R[0] * R[0];
            if (target_dist_sq == R1_sq) {
                 std::cout << "Yes" << std::endl; // Possible only if distance equals radius.
            } else {
                 std::cout << "No" << std::endl; // Not possible otherwise.
            }
        } else {
             // For N >= 2, the problem condition is satisfiable if and only if the distance to the target point D_P 
             // is less than or equal to the maximum possible reach K, where K = 2 * Sum(R_i) - min(R_i).
             // We compare the squared distance D_P^2 with K^2.
            
            // Calculate the maximum reach value K.
            __int128_t K = 2 * sum_R - min_R;
            
            // Calculate K squared. This computation requires __int128_t because K can be up to ~4e10, 
            // so K^2 can be up to ~1.6e21, which exceeds the capacity of long long.
            __int128_t K_sq = K * K;

            // Check if the target point's squared distance from the origin is within the squared maximum reach.
            if (target_dist_sq <= K_sq) {
                std::cout << "Yes" << std::endl; // Possible if target is within reach.
            } else {
                std::cout << "No" << std::endl; // Not possible if target is beyond reach.
            }
        }
    #endif // HAS_INT128 check closes here

    return 0; // Indicate successful execution.
}
0