BOJ 1709 타일 위의 원

일단 $N$이 짝수이므로, 원의 중심을 원점으로 놓으면 $N$을 2로 나눈 값 $R$을 반지름으로 하는 원이 1사분면 위에서 통과하는 단위 정사각형의 개수를 세서 4배하면 됩니다.

1사분면 위에서 $y$축 위의 점에서 시작한 원호는 $x$축 위의 점에 도달할 때까지 오른쪽 또는 아래로만 이동하므로, 원호가 통과하는 단위 정사각형 하나가 있을 때 다음 칸은 그 칸의 오른쪽 칸, 아래 칸, 오른쪽 아래 칸 중 하나입니다. 또한, 이 과정에서 오른쪽으로 $R-1$번, 아래로 $R-1$번 이동하므로, $2(R-1) + 1$에서 오른쪽 아래 칸으로 이동한 횟수를 빼면 원호가 통과하는 칸의 총 개수를 알 수 있습니다.

오른쪽 아래 칸으로 이동하는 경우는 원호가 어떤 격자점을 지나갈 때이므로, 각각의 $x$에 대해 $R^2 - x^2$이 제곱수인지 판별하여 그러한 격자점의 개수를 셀 수 있습니다.