r1과 r2가 주어지면, r1에 해당하는 원과 r2에 해당하는 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 리턴하는 문제
일단 r1 < r2의 관계이기 떄문에 R1과 r2사이의 정수 좌표는 8개를 디폴트로 하고 시작한다 상하좌우 x좌표와 y좌표에 걸쳐있는 쪽은 무조건 사이에 있으면서도 반지름이 정수이기 때문에 x좌표와 y좌표 모두 걸쳐져 있는 좌표가 정수로 되어있기 때문이다 그렇다면 그 사이에 있는 것들이 문제인데..
요렇게 생긴 두 원의 사이에서 해당 원은 무조건 원점을 기준으로 하는 원이기 때문에 4가지의 영역 모두 사이에 있는 정수 x, y좌표가 서로의 부호만 다를 뿐이지 사실상 절대값으로 따지면 모두 같은 위치이다.
따라서 굳이 하나하나 다 구하기 보다는, 한쪽을 구해놓고 x4를 하는 편이 합리적으로 보인다.
그럼 이제 남은 문제는 이 사이의 값을 어떻게 구할 것이냐인데,,
- 더 큰 원을 지나는 x좌표와 y좌표를 모두 구한다?
- 1,000,000까지 반지름의 길이가 될 수 있는데 이걸 모두 구하는 것은 비합리적이라고 생각해서 일단 보류
- 큰 원 안의 정수 좌표들에서 작은 원의 조건을 뺀 다음 거리를 계산해서 원 세기
- 작은 쪽의 원의 반지름만큼의 길이를 가진 정사각형부터 시작한다면, 조건의 수를 확실히 줄일 수 있다
2번 방식대로 풀 경우,
- 작은 원의 반지름을 구해서 정사각형의 각 변부터 시작 (큰 원의 반지름 - 작은 원의 반지름)
- x좌표와 y좌표를 하나씩 올려가면서 큰 원 안에 들어오는지 확인
- 큰 원 안에 들어오는 경우는 피타고라스의 정리를 이용하여 구한 대각선이 큰 원의 반지름보다 작아야 함
a^2 + b^2 = r^2 r^2 -a^2 = b