[백준] 15328 : 산타의 선물

https://www.acmicpc.net/problem/15328

문제 분석

 3차원에서 원점부터 4개의 지점을 순차적으로 방문할 때 총 이동거리가 X보다 큰지 작은 지를 묻는 문제이다.
단순히 각 지점간 거리를 더해서 X와 대소 비교를 하면 되어 보이지만 문제가 long double보다 더 높은 정밀도를 써야 하여 16바이트 자료형인 __float128을 사용해야 하고 그에 따라 거리를 구하기위해 필요한 sqrt함수도 직접 구현해야 한다.  
$($파이썬의 경우 decimal 자료형을 사용하면 자료형 자체에서 sqrt를 지원하여 쉽게 구현가능$)$

문제 해결 전략

 __float128을 사용하고  sqrt 함수를 구현하는 것이 문제의 전부이다. 제곱근은 바빌로니아 방식을 사용하거나 뉴턴 랩슨방식을 통해 구하면 된다. 결국 최종식은 동일하니 아래에는 뉴턴 랩슨 방식의 유도만 기술한다. 하단의 방식을 사용하여  $x_n=x_{n+1}$이 될 때까지 재귀적으로 반복하면 된다.

문제는 a의 제곱근인 x를 구하는것
$x=\sqrt(a) \rightarrow x^2-a=0$
아래 함수가 0이 되도록 하는 x를 찾는 문제와 동일
$f(x)=x^2-a$
뉴턴 랩슨에 따라 아래식을 재귀적으로 구하면 해결
다만, 음수가 안 나오게끔 초기값은 임의의 양수로 설정
$x_{n+1}=x_n-\frac {f(x_n)}{f'(x_n)}=x_n-\frac {x_n^2-a}{2x_n}=\frac {x_n-a/x_n}{2}$

또한, 코드에서는 값을 합할 때 오차를 줄이기 위해 kahan summation의 방식을 사용했는데 더하는 수가 적어서 그냥 생략하고 바로 더해버려도 된다. 

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

//문제분석
//문제 자체는 거리의 합을 구해서 그게 X보다 작은지 확인하는 간단한 문제이지만
//long double로도 소화안되는 극한의 정밀도를 요구하여 
//__float128의 사용과 sqrt의 구현을 강제함 
//=====================================================================
//해결전략
//sqrt 구현만하면 끝이다.
//=====================================================================
//필요자료형
//변수
//
//함수
//
typedef __float128 f128;
int T;
vector<char*> answers;

f128 kahan_sum(f128 dist1, f128 dist2, f128 dist3, f128 dist4) {
    f128 sum = 0;
    f128 c = 0;
    f128 nums[4]={dist1,dist2,dist3,dist4};
    for (size_t i = 0; i < 4; i++)
    {
        f128 x=nums[i];
        f128 y = x - c;
        f128 t = sum + y;
        c = (t - sum) - y;
        sum = t;
    }
    return sum;
}

f128 sqrt_f128(f128 x){
    f128 ret = x;
    if (x==0) return ret; 
    while(ret!=(ret+x/ret)/2){
        ret=(ret+x/ret)/2;
    }
    return ret;
}

f128 GetDist(int A, int B, int C){
    f128 dist = sqrt_f128(A*A+B*B+C*C);
    return dist;
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> T;
    for (size_t i = 0; i < T; i++)
    {
        int X;
        int A1, B1, C1;
        int A2, B2, C2;
        int A3, B3, C3;
        int A4, B4, C4;

        cin >> X;
        cin >> A1 >> B1 >> C1;
        cin >> A2 >> B2 >> C2;
        cin >> A3 >> B3 >> C3;
        cin >> A4 >> B4 >> C4;

        f128 dist=kahan_sum(
            GetDist(A1,B1,C1),
            GetDist(A2-A1,B2-B1,C2-C1),
            GetDist(A3-A2,B3-B2,C3-C2),
            GetDist(A4-A3,B4-B3,C4-C3)
        );
        
        answers.push_back(
            (char*)((dist<=X) ? "YES" : "NO")
        );
    }

    for(auto ans : answers) cout << ans << "\n";   
}