시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 140 | 22 | 15 | 14.851% |
시작 곡선 | 변형 1 | 변형 2 | 변형 3 | 변형 4 | |
---|---|---|---|---|---|
H1 | |||||
H2 | |||||
H3 | |||||
H4 |
힐베르트 곡선은 독일 수학자 다비드 힐베르트가 처음으로 묘사한 연속 프랙탈 공간 채움 곡선이다.
힐베르트 곡선은 가로줄과 세로줄로 이루어져 있는 곡선의 수열 H1, H2, H3, H4, ...을 이용해서 만들 수 있다. 각각의 곡선은 단위 정사각형 [0, 1] × [0, 1]위에 있다.
H1은 (¼, ¾), (¼, ¼), (¾, ¼), (¾, ¾)을 잇는 세 선분으로 이루어져 있다. Hn은 Hn-1을 이용해서 다음 4가지 과정을 통해서 재귀적으로 만들 수 있다.
1. Hn-1의 모든 좌표를 절반으로 줄인다.
2. 곡선을 (0, ½)을 기준으로 반시계 방향으로 돌린 곡선을 더한다.
3. x = ½를 기준으로 대칭시킨 곡선을 더한다.
4. m = ½n+1이라 하자. 각 곡선의 끝점 (½ - m, ½ - m) 와 (½ + m, ½ - m), (m, ½ - m) 와 (m, ½ + m), (1 - m, ½ - m) 와 (1 - m, ½ + m)을 잇는다.
수평선이 주어졌을 때, 곡선과 교차하는 점의 수를 구하는 프로그램을 작성하시오. 예를 들어, 입력 예제 첫 번째와 두 번째 그림은 다음과 같다.
그림 1 | 그림 2 |
---|---|
H3과 수평선(2/8,7/8)-(7/8,7/8)은 3번 교차한다 | H4과 수평선(0/16,1/16)-(16/16,1/16)은 16번 교차한다 |
Hn의 꼭짓점 좌표는 항상 1/2n+1의 홀수 배수이다. 수평선의 끝점 좌표는 항상 1/2n의 배수이다. 따라서, 선분은 항상 Hn의 세로선과 교차한다.
입력은 여러 개의 데이터로 이루어져 있다. 주어지는 데이터는 최대 100개이다. 각 데이터는 다음과 같은 Hn과 수평선(x1/2n, y/2n)-(x2/2n, y/2n)을 나타내는 4개의 수(n x1 x2 y)가 공백으로 구분되어져 있다. (0 < n < 31, x1 < x2) x1, x2, y는 항상 [0, 2n] 범위이다.
마지막 데이터의 다음 줄에는 0이 하나 주어진다.
각 데이터에 대해서 Hn과 주어진 수평선과 교차하는 점의 개수를 출력한다.
3 2 7 7 4 0 16 1 30 1 1073741823 1 0
3 16 1073741822
ICPC > Regionals > North America > Mid-Central Regional > 2002 Mid-Central Regional Programming Contest B번