레이팅 미적용농부 존의 취미인 고에너지 물리 실험이 역효과를 일으켜, 농장에 N개의 웜홀 (2 <= N <= 12, N은 짝수)이 생겨났다. 각 웜홀은 농장의 2차원 지도 위 서로 다른 점에 위치한다.
웜홀들은 N/2개의 연결된 쌍을 이룬다. 웜홀 A와 B가 한 쌍으로 연결되어 있으면, 웜홀 A로 들어간 물체는 같은 방향으로 이동하면서 웜홀 B에서 나오고, 그 반대도 마찬가지이다. 예를 들어 (0,0)에 웜홀 A, (1,0)에 웜홀 B가 쌍으로 연결되어 있고, 소 베시가 (½,0) 위치에서 +x 방향으로 이동하기 시작한다고 하자. 베시는 웜홀 B로 들어가 A에서 나오고, 다시 B로 들어가는 식으로 무한 순환에 갇히게 된다!
농부 존은 베시가 항상 +x 방향으로 걷는다는 것은 알지만, 베시가 현재 어디에 있는지는 기억하지 못한다. 베시가 운 나쁜 위치에서 출발할 경우 무한 순환에 갇힐 가능성이 있는, 서로 다른 웜홀 짝짓기의 가짓수를 세는 것을 도와주시오.
첫째 줄에 웜홀의 수 N이 주어진다.
둘째 줄부터 1+N번째 줄까지, 각 줄에 웜홀 하나의 (x,y) 좌표를 나타내는 공백으로 구분된 두 정수가 주어진다. 각 좌표는 0..1,000,000,000 범위이다.
어떤 출발점에서 +x 방향으로 걷던 베시가 순환에 갇힐 가능성이 있는, 서로 다른 웜홀 짝짓기의 가짓수를 출력한다.
wormhole.in · 출력을 쓸 파일 wormhole.out4
0 0
1 0
1 1
0 12Output details: The pairings (1-2, 3-4) and (1-3, 2-4) can trap Bessie; only (1-4, 2-3) is safe.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > December > Bronze