레이팅 미적용매일 농부 존(Farmer John)은 N마리 (1 <= N <= 10)의 소들의 건강과 안녕을 확인하기 위해 농장을 돌아다닌다.
각 소의 위치는 2차원 평면의 점으로 표현되며, 농부 존은 원점 (0,0)에서 출발한다. 산책을 더 흥미롭게 만들기 위해, 농부 존은 좌표축에 평행한 방향으로만, 즉 북, 남, 동, 서로만 걷기로 했다. 게다가 존은 소의 위치에 도달했을 때만 진행 방향을 바꾼다 (원한다면 방향을 바꾸지 않고 소의 위치를 그냥 지나칠 수도 있다). 방향을 바꿀 때는 90도 회전 또는 180도 회전을 할 수 있다. FJ의 경로는 모든 소를 방문한 후 반드시 원점으로 돌아와야 한다.
각 소의 위치에서 정확히 한 번씩 방향을 바꾼다고 할 때, FJ가 N마리의 소를 방문할 수 있는 서로 다른 경로의 수를 계산하시오. 방향을 바꾸지 않고 소의 위치를 지나치는 것은 몇 번이든 허용된다. 같은 기하학적 경로라도 정방향과 역방향은 서로 다른 두 경로로 센다.
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 i번째 점의 x 좌표와 y 좌표(공백으로 구분)가 주어진다 (각 값은 -1000...1000 범위).
FJ가 택할 수 있는 서로 다른 경로의 수 (유효한 경로가 없으면 0일 수도 있다).
connect.in · 출력을 쓸 파일 connect.out4
0 1
2 1
2 0
2 -52Input details: There are 4 cows, at positions (0,1), (2,1), (2,0), and (2,-5).
Output details: There are two different routes: Farmer John can visit cows in the orders 1-2-4-3 or 3-4-2-1 before returning to the origin.