Level 2. 두 원 사이의 정수 쌍

Level 2. 두 원 사이의 정수 쌍

 

 

1사분면에 해당하는 점의 개수를 구한 후 4를 곱하는 방식이다.

 

x를 1 ~ r₂까지 증가시키면서 삼각함수를 이용해 원₁의 y₁좌표, 원₂의 y₂좌표를 구한다.

 

두 y좌표를 빼 계산한 값이 x = t에서의 점 개수이고 이것을 반복해 더해 정답을 구한다.

 

그런데 40%밖에 정답 처리되지 않았다..

 

복잡한 코드도 아니라서 어디가 문제인지 도통 감이 안 잡히고, 아무래도 삼각함수 값을 구하는 과정에서 오차로 인해 문제가 발생하는 것 같다.

 

// 이 풀이는 틀린 풀이다.
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

long long solution(int r1, int r2)
{
    long long answer = 0;

    for (double x = 1; x <= r2; ++x)
    {
        double theta1 = acos(min(x / r1, 1.0));
        double theta2 = acos(x / r2);

        double Y1 = r1 * sin(theta1);
        double Y2 = r2 * sin(theta2);

        answer += floor(Y2) - ceil(Y1) + 1;
    }

    return answer * 4;
}

 

첫 번째 방법과 동일하게 높이를 이용하는 방법인데, 삼각함수 대신 제곱근을 이용해 높이를 직접 구하면 정답 처리된다.

 

제곱을 매번 계산하지 않기 위해 메모를 사용했다.

 

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

using namespace std;

long long solution(int r1, int r2)
{
    long long answer = 0;
    vector<double> memo(r2 + 1);

    for (double n = 0; n <= r2; ++n)
        memo[n] = n * n;

    for (int x = 1; x <= r2; ++x)
    {
        double Y1 = sqrt(max(memo[r1] - memo[x], 0.0));
        double Y2 = sqrt(memo[r2] - memo[x]);

        answer += floor(Y2) - ceil(Y1) + 1;
    }

    return answer * 4;
}