1709 타일 위의 원

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

1709번: 타일 위의 원

---

접근

둘레가 그려져 있는 타일의 개수를 구하라는 문제다. 원에 대한 공식이 필요한가 싶었는데 문제 이곳저곳에 힌트가 있었다.

 

N의 범위가 150,000,000이란다. 1번씩 반복을 돌려도 1억 5천만?? 말이 되나 싶어 시간 제한을 봤더니 5초나 주더라.

 

즉, 하나하나 세어가며 풀어도 된다는 내용같다. 그래도 N*N의 범위를 모두 탐색하는건 아니라고 생각하여 어떤 방법이 가능할까 고민했다. 

 

처음 생각한 방법은 이렇다. 타일과 원의 중심간의 거리를 따져 해당 타일에 원의 둘레가 있는지 검사하는 것이다.

 

원은 대칭성을 가지기 때문에 4분의 1부분만 검사해도 나머지 부분에 몇 개가 있는지 알 수 있다. 

 

타일 내에 원의 둘레가 있다는 것은 타일과 중심 간의 거리가 원의 반지름보다 짧을 것이다. 타일 내에 원의 둘레가 없다는 것은 타일과 중심 간의 거리가 원의 반지름보다 길 것이다.

 

원의 중심을 (0,0)으로 설정했을 때 아래 사진처럼 거리를 따져보면 원의 둘레가 그려져있는지 대략 판단할 수 있다.

배경 출처 : desmos.com

 

타일의 왼쪽 아래 좌표와 (0,0)까지의 거리를 재어보면, 거리가 반지름보다 길 때 원의 둘레를 포함하지 않고, 반지름보다 작을 때 원의 둘레를 포함한다. 따라서 (0,N-1)부터 (N,0)까지 좌표를 이동하되, 원의 둘레를 포함하는 좌표만 선택해가며 개수를 세면 된다.

 

현재 좌표에서 x값을 1만큼 더한 좌표와 (0,0)까지의 거리가 원의 둘레보다 짧다면 해당 좌표는 원의 둘레를 포함한다. 따라서 현재 좌표에서 x값을 1만큼 바꾼다. 

현재 좌표에서 x값을 1만큼 더한 좌표와 (0,0)까지의 거리가 원의 둘레보다 짧다면 해당 좌표는 원의 둘레를 포함하지 않는다. 따라서 현재 좌표에서 y값을 1만큼 바꾼다.

배경 출처 : desmos.com

 

주의할 점은 원의 둘레에 좌표가 있는 경우인데, 위 사진 처럼 N이 26이고 (5,12)좌표에 도달했을 때를 말한다. 

 

이 때는 x값을 1만큼 더하거나 y값을 1만큼 빼도 원의 둘레를 포함하지 않으므로 x,y모두 변화시켜야한다.

미흡했던 점

없었다! 

---

#include <iostream>
#define LL long long
LL dist(LL x, LL y) { return x * x + y * y; }
int main() {
  LL N, x = 0, y, R, cnt = 0;
  scanf("%lld", &N);
  N /= 2;
  y = N - 1;
  R = N * N;
  while (x <= N && y >= 0) {
    LL downLeftDist = dist(x + 1, y);
    if (downLeftDist <= R)
      x++;
    if (downLeftDist >= R)
      y--;
    cnt++;
  }
  printf("%lld", cnt * 4);
}