24684번 - 평면을 채우는 오각형

문제

평면을 채울 수 있는 정다각형은 정삼각형, 정사각형, 그리고 정육각형뿐이다. 하지만 정오각형이 아닌 오각형 중에서는 평면을 채울 수 있는 오각형이 있다. 다음과 같이 한 변의 길이가 1인 정사각형에, 정사각형의 한 변을 빗변으로 하는 직각이등변삼각형을 붙인 모양은 평면을 채울 수 있다.

이 오각형의 사각중심은, 직각이등변삼각형을 붙이기 전 정사각형의 중심으로 정의한다. 이 다각형을 이용하여 다음과 같이 평면을 채울 것이다.

• 먼저 직각이등변삼각형 부분 네 개를 모아 십자가 모양을 만든다.

• 그다음 십자가들을 이어붙인다. 이때, 이웃한 두 십자가의 중심을 이었을 때 $(2,1), (-2,-1), (-1,2), (1,-2)$ 중 한 방향을 바라보도록 이어 붙인다.

이 타일링에서 오각형들을 정점으로 보고, 한 변을 공유하는 오각형끼리 간선으로 연결하여 생기는 무한 그래프를 생각하자.

이 무한 그래프의 두 정점 사이의 거리를 구하는 프로그램을 작성하여라. 정점은 2차원 상의 점 $(x,y)$로 나타내되, $(x,y)$가 오각형의 사각중심이 되도록 한다. $(0,0)$에는 십자가 하나의 중심이 위치한다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$줄에 두 오각형의 사각중심의 좌표 $x_1, y_1, x_2, y_2$가 주어진다.

출력

각 테스트 케이스마다 두 오각형의 그래프상에서의 거리를 한 줄에 하나씩 출력한다.

제한

• 1ドル \le T \le 100,000円$
• $-10^{18} \le x_1, y_1, x_2, y_2 \le 10^{18}$
• 2ドルx_1+y_1 \not\equiv 0\ (\textrm{mod}\ 5)$
• 2ドルx_2+y_2 \not\equiv 0\ (\textrm{mod}\ 5)$

힌트