벌집우주와 쿼리

시간 제한1초메모리 제한1024 MB

요약
육각 격자에서 로켓이 원점에서 0도 방향으로 출발해 주어진 좌표에 도달할 때 필요한 최소 방향 전환 횟수를 각 좌표마다 구한다.
난이도

보통10점 중 5점

유형
수학, 기하, 구현
정답자
아직 제출이 없습니다

문제

pjshwa는 로켓을 타고 광활한 벌집우주를 여행하고 있다. 벌집우주는 아래 그림과 같은 좌표계를 사용한다.

(x,y)(x, y)에 위치한 로켓은 방향각 r∘r^\circ와, 이동할 거리 tt를 정하여 다음 6가지 좌표 중 하나로 갈 수 있다.

방향각 r∘r^\circ이동 후 좌표
0∘0^\circ(x+t,y)(x + t, y)
60∘60^\circ(x+t,y+t)(x + t, y + t)
120∘120^\circ(x,y+t)(x, y + t)
180∘180^\circ(x−t,y)(x - t, y)
240∘240^\circ(x−t,y−t)(x - t, y - t)
300∘300^\circ(x,y−t)(x, y - t)

멀미가 심한 pjshwa는 로켓의 방향을 가능한 적게 바꾸고 싶다. 가고 싶은 좌표 QQ개가 주어질 때, (0,0)(0, 0)에서 0∘0^\circ 방향으로 놓여 있는 로켓이 그 좌표에 도달하기 위해 필요한 최소 방향 전환 횟수를 계산하자!

입력

첫 번째 줄에 pjshwa가 가고 싶어 하는 좌표의 개수 QQ가 주어진다. (1≤Q≤100,000)(1 \leq Q \leq 100\\,000)

두 번째 줄부터 QQ개의 줄에 걸쳐 좌표를 나타내는 정수 x,yx, y가 공백으로 구분되어 주어진다. (−109≤x,y≤109)(-10^9 \leq x, y \leq 10^9)

출력

각 좌표마다 (0,0)(0, 0)에서 0∘0^\circ 방향으로 놓여 있는 로켓이 해당 좌표에 도달하기 위해 필요한 최소 방향 전환 횟수를 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    2
3 0
1 2
    예상 출력
    0
1

  2. 예제 2

    입력
    3
0 0
-5 7
-2 -1
    예상 출력
    0
2
2