[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^{\prime },y^{\prime }+1),[x^{\prime },x^{\prime }+1)$로 표현할 수 있습니다.

 

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

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

 

$y$가 $y^{\prime }$부터 $y^{\prime }+1$이라면, 이에 대응하는 $x$는

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

 

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

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

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

굳이 반열린 구간으로 한 이유는, 닫힌 구간으로 하면 정확히 한 점을 지날 때의 케이스 ($\sqrt{R^2-y^{\prime 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;
}