시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB163313022.901%

문제

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 순례자는 위치한 성지에서 다른 성지로 이동하고, 성지에 도착할 때마다 신께 기도를 드린다.

지상의 중앙에는 대성지가 있어, 대성지를 기준으로 성지들이 일정한 간격으로 나열되어 있다. 어떤 성지의 위치는 $(X,Y)$로 나타낼 수 있는데, 이 성지가 대성지로부터 동쪽으로 $X$마일 ($X < 0$인 경우, 서쪽으로 $-X$마일), 북쪽으로 $Y$마일 ($Y < 0$인 경우, 남쪽으로 $-Y$마일) 떨어진 곳에 있다는 뜻이다. 여기서 마일이란, 신이 천 걸음 걸었을 때 이동한 거리를 뜻한다.

그렇게 $-2^{31} \leq X,Y < 2^{31}$인 모든 정수 $X,Y$에 대해 $(X,Y)$에 성지가 존재하며, 지상에는 정확히 $2^{64}$ 개의 성지가 있게 된다.

순례자는 이 중 $N$ 개의 성지를 선택하여 순서대로 순례한 다음 처음으로 선택한 성지로 돌아오려고 한다. 이 성지들의 위치는, 완벽한 신이 가장 좋아하는 완벽한 모양인 정$N$각형을 본떠서 선택할 것이다. 정$N$각형의 특징은 매우 많지만, 대표적으로 다음과 같은 것이 있다.

  • 볼록 다각형이다.
  • 모든 변의 길이가 같다.
  • 모든 각의 크기가 같다.

순례자는 선택한 성지들이 정$N$각형 모양을 이루도록 하고 싶었지만, 문제점이 있었다. $i$번째로 선택한 성지의 위치를 $(X_i, Y_i)$로 표현할 때, $X_i, Y_i$가 모두 정수이기 때문에 정$N$각형을 완벽히 만들지 못할 수도 있다는 사실을 깨달았기 때문이다.

그래서 그 대신 조건을 완화하여 다음의 조건을 만족하도록 성지를 선택하려고 한다. 편의를 위해서 $N+i$번째 성지와 $i$번째 성지를 같은 것으로 생각한다.

  • $i$ 번째, $i+1$ 번째, $i+2$ 번째 성지가 반시계방향으로 위치해 있다.
  • $i$ 번째와 $i+1$ 번째 성지간의 유클리드 거리를 $L_i = \sqrt{(X_i - X_{i+1})^2 + (Y_i - Y_{i+1})^2}$ 라고 하자. 이 때, $1$ 이상 $N$이하의 정수 $i$에 대해, $L_i = L_1$을 만족하는 $i$가 $K$ 개 이상 존재해야 한다.
  • $2$ 이상 $N-2$ 이하의 $k$에 대해, $i$ 번째 성지와 $i+1$ 번째 성지를 연결하는 선분과, $i+k$ 번째 성지와 $i+k+1$ 번째 성지를 연결 하는 선분은 서로 만나서는 안된다.

순례자가 조건을 만족하면서 $N$ 개의 성지를 선택할 수 있는지 없는지의 여부를 구하고, 선택할 수 있다면 어떤 위치에 있는 성지들을 어떤 순서로 선택해야 하는지 구하여라

입력

첫 번째 줄에, 선택할 성지의 개수와 성지의 거리에 대한 조건을 나타내는 두 자연수 $N$, $K$ ($3 \le N \le 2\ 500, 1 \le K \le N$)가 주어진다.

출력

첫 번째 줄에 조건을 만족하면서 $N$ 개의 성지를 선택할 수 있는지 없는지의 여부를 YES혹은 NO로 출력한다.

성지를 선택할 수 있는 경우, 다음 줄부터 시작하여 $N$ 개의 줄에 걸쳐 선택한 성지들의 위치를 출력한다. $i$ 번째 줄에는 $i$ 번째로 선택된 성지의 위치를 나타내는 두 정수 $X_i$와 $Y_i$를 공백으로 구분하여 출력한다. 출력된 모든 위치에 성지가 존재해야만 정답으로 인정된다.

서브태스크 1 (1점)

  • $3 \le N \le 2500$
  • $K = 1$

서브태스크 2 (10점)

  • $3 \le N \le 12$

서브태스크 3 (100점)

  • $3 \le N \le 2500$

예제 입력 1

4 3

예제 출력 1

YES
0 0
13 0
8 12
5 12

이 예제에서의 성지의 위치는 다음 조건을 만족한다.

  • 모든 위치는 정수로 표현된다.
  • 성지가 1번부터 4번까지 반시계방향 순서로 배치되어 있다.
  • $L_1 = L_2 = L_4 = 13$, $L_3 = 3$ 이고, $L_1$과 길이가 같은 $L_i$가 $L_1$, $L_2$, $L_4$ 총 세 개 존재한다.

예제 입력 2

3 3

예제 출력 2

NO

세 조건을 모두 만족하는 정삼각형 모양의 배치로 성지를 건설하는 방법은 존재하지 않는다.

출처

Contest > BOJ User Contest > 전시관 > 제1 전시관 6번

채점 및 기타 정보

  • 예제는 채점하지 않는다.