페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3862
다국어

웜홀 (Wormholes) 1초 128MB

문제

농부 존의 물리 실험 취미가 역효과를 일으켜 짝수 N(2 \le N \le 12)개의 웜홀이 그의 농장에 생겼습니다. 각각의 웜홀은 농장의 2D 지도에서 고유한 지점에 위치해 있습니다.

농부 존의 계산에 따르면, 웜홀은 \frac{N}{2}개의 연결된 쌍을 형성합니다. 예를 들어, 웜홀 A와 B가 쌍으로 연결되어 있으면, A에 들어간 물체는 같은 방향으로 B에서 나오고, B에 들어간 물체는 같은 방향으로 A에서 나옵니다.

이러한 특성은 무한 루프에 빠질 가능성이 있습니다.

예를 들어, 웜홀 A가 (0,0)에 있고 웜홀 B가 (1,0)에 있으며, 소 Bessie가 (\frac12,0) 지점에서 +x 방향으로 이동을 시작하면 Bessie는 B로 들어가 A로 나오고, 다시 B로 들어가 A로 나오는 무한 루프에 빠지게 됩니다.

농부 존은 그의 농장에서 각 웜홀의 정확한 위치를 알고 있습니다. 또한, 소 Bessie가 항상 +x 방향으로 걷지만, Bessie가 현재 어디에 있는지는 알지 못합니다.

농부 존을 도와 Bessie가 불행하게도 무한 사이클에 빠질 수 있는 웜홀 쌍의 개수를 세어주세요.


입력

  • 첫 번째 줄: 웜홀의 수 N.

  • 두 번째 줄부터 N+1번째 줄까지: 각 줄에는 공백으로 구분된 두 정수 (x, y)가 주어지며, 이는 하나의 웜홀의 좌표를 나타냅니다. 각 좌표는 0 이상 1,000,000,000 이하의 값을 가집니다.


출력

  • 첫 번째 줄: Bessie가 +x 방향으로 걸을 때 무한 사이클에 빠질 수 있는 웜홀 쌍의 개수.


예제1

입력
4
00
10
11
01
출력
2

4개의 웜홀이 정사각형의 모서리를 형성합니다.

웜홀을 1, 2, 3, 4로 번호를 매겼을 때, 1-2와 3-4 또는 1-3과 2-4로 쌍을 이룰 경우 Bessie는 무한 루프에 빠질 수 있습니다.

단지 1-4와 2-3으로 쌍을 이루면 Bessie는 어떤 출발점에서도 무한 루프에 빠지지 않습니다.


출처

USACO 2013 December Bronze

역링크