[BOJ 1709] 타일 위의 원

체감 난이도: Silver I + 0.1

 

태그

• Geometry (기하)
  • Pythagoras Theorem (피타고라스의 정리)

 

풀이

1. 원은 굉장히 대칭적인데, 이를 사용해서 작업을 편하게 할 수 있을까?

\( x \)축과 \( y \)축 대칭을 사용해, 우측 상단의 1/4 부분만 고려해주면 됩니다.

마침 길이가 짝수라고 하니, 1/4로 잘 나눠짐을 볼 수 있습니다.

 

잘 고민해보면 \( y = x \) 직선까지 고려해서 1/8 대칭을 만들 수는 있지만, 오히려 작업이 귀찮아지므로 위의 1/4만 고려하도록 합시다.

 

2. 타일을 다루기 쉬운 걸로 바꿔보자.

타일이라고 하니까, 뭔가 \( (r, c) \)라는 하나의 좌표를 주고 싶게 생겼습니다.

하지만, 타일 하나에 좌표 하나를 주게 되면, 뭔가 다음 단계가 잘 되지 않게 되는데...

 

대신에, 하나의 타일을 하나의 직사각형으로 봅시다.

세로로는 \( [y_1, y_2) \), 가로로는 \( [x_1, x_2) \) 구간을 덮고 있는 직사각형으로요.

 

각 타일의 크기는 \( 1 \times 1 \)이므로, \( [y', y'+1), [x', x'+1) \)로 표현할 수 있습니다.

 

3. 특정 y좌표를 가지고 있는 칸들 중, 원이 지나는 칸은 어떻게 될까?

지금부터 편의상 반지름 \( R = \frac{N}{2} \)을 정의하겠습니다.

 

\( y \)가 \( y' \)부터 \( y'+1 \)이라면, 이에 대응하는 \( x \)는

\( \sqrt{R^2 - (y'+1)^2} \)부터 \( \sqrt{R^2 - y'^2} \)까지가 됩니다.

 

이제 두 경우로 나눠봅시다.

• \( \sqrt{R^2 - y'^2} \)가 정수인 경우: \( \left\lfloor \sqrt{R^2 - y'^2} \right\rfloor \)번 칸은 칠해지지 않습니다.
• \( \sqrt{R^2 - y'^2} \)가 정수가 아닌 경우: \( \left\lfloor \sqrt{R^2 - y'^2} \right\rfloor \)번 칸까지 칠해줘야 합니다.

이는 아까 위에서 정의한 타일의 구간이 반열린 구간이기 때문입니다.

굳이 반열린 구간으로 한 이유는, 닫힌 구간으로 하면 정확히 한 점을 지날 때의 케이스 (\( \sqrt{R^2 - y'^2} \)가 정수인 경우)를 제대로 처리할 수 없기 때문입니다.

 

코드

코드에서는 \( y \)를 내려가면서 계산하므로, \( y_1, x_1 \)과 \( y_2, x_2 \)의 순서가 바뀌었습니다.

즉, \( y_1 > y_2 \)이고, \( x_1 > x_2 \)입니다.

void Main(){
    ll r; cin >> r; r /= 2;
    ll ans = 0;
    ll x1 = 0, y1 = r;
    for (ll y2 = r-1; y2 >= 0; y2--){
        ll x2 = x1;
        while ((x2+1)*(x2+1) + y2*y2 <= r*r){ x2 += 1; }
        if (x2*x2 + y2*y2 == r*r){ ans += x2-x1; }
        else{ ans += x2-x1+1; }
        y1 = y2; x1 = x2;
    }
    cout << ans*4;
}