Tag: divide and conquer

...
		num = 2 ** (N - 1)
		# 좌상단
    if x <= num and y <= num:
        position(N-1, x, y, base)
        
		# 우상단
    elif x > num and y <= num:
        position(N-1, x - num, y, 4 ** (N - 1) + base)
    
		# 좌하단
    elif x <= num and y > num:
        position(N-1, x, y - num, 2 * 4 ** (N - 1) + base)
        
		# 우하단
    elif x > num and y > num:
        position(N-1, x - num, y - num, 3 * 4 ** (N - 1) + base)

위와 같이 한 변이 $2^n$인 영역이 주어졌을 때 각 변을 직각 이등분 하는 선은 가장 좌상단의 꼭짓점에서 $2^n/2(=2^{n-1})$ 만큼 떨어져 있는 것을 확인할 수 있다. 그러므로 x, y가 $2^{n-1}$보다 큰지 작은지 확인하면 네 개의 영역 중 어디에 속해있는지 알 수 있다. 단 여기서 x는 커질수록 오른쪽, y는 커질수록 아래로 진행한다고 생각해야 한다.