두 원 사이의 정수 쌍

문제 설명

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.

※ 각 원 위의 점도 포함하여 셉니다.

 

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

입출력 예

r1	r2	result
2	3	20

---

문제 해설

그냥 수학과 좌표계산에 대해 좀 더 좋은 이해도를 가지고 있는지 테스트 하는 문제이다.

Collision에 대해 기본적인 이해만 있으면 풀 수 있다.

 

거기에 좀 더 효율적인 코딩방식으로 풀어야한다.

---

첫 번째 시도

#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0;
    long long Rec1 = r2 * 2 - 1;
    long long Rec2 = r1 * 2 - 1;

    answer = pow(Rec1, 2) - pow(Rec2, 2);
    return answer + 4;
}

실패

 

귀찮아서 대충풀었다가 틀렸다. 당연히 틀린문제

---

두 번째 시도

#include <string>
#include <vector>
#include <cmath>

using namespace std;

bool CollisionChack(const int& S, const vector<int>& input, bool out = true)
{
    if(out)
        return sqrt(pow(input[0], 2) + pow(input[1], 2)) <= S;
    return sqrt(pow(input[0], 2) + pow(input[1], 2)) < S;
}

long long solution(int r1, int r2) {
    long long answer = 0;
    for (int x = -r2; x <= r2; x++)
        for (int y = -r2; y <= r2; y++) 
            if (CollisionChack(r2, { x, y }) && !CollisionChack(r1, { x, y }, false))
                answer++;
    return answer;
}

실패

시간초과가 나타났다. Collision을 그냥 전부다 돌려버리면 문제가 생긴다. 좀 더 효율적으로 풀어야한다.

---

세 번째 시도

#include <string>
#include <vector>
#include <cmath>

using namespace std;

bool CollisionChack(const int& S, const vector<int>& input, bool out = true)
{
    if (out)
        return pow(input[0], 2) + pow(input[1], 2) <= pow(S, 2);
    return pow(input[0], 2) + pow(input[1], 2) < pow(S, 2);
}

long long solution(int r1, int r2) {
    long long answer = 0;
    int x = r2;
    for (int y = 1; y < r2; y++)
    {
        while (!CollisionChack(r2, { x, y })) --x;
        answer += x;
    }
    answer = (answer + r2) * 4 + 1;

    long long in = 0;
    x = r1;
    for (int y = 1; y < r1; y++)
    {
        while (!CollisionChack(r1, { x, y }, false)) --x;
        in += x;
    }
    answer -= (in + r1 - 1) * 4 + 1;
    return answer;
}

성공

어차피 원은 대칭이니까, 한귀퉁이만 구하고 4를 곱해주면된다.