프로그램 명: usa_wormholebron
제한시간: 1 초

농부존의 고에너지 물리학 실험이 터져서 그의 농장 위에 N 개의 웜홀(2<=N<=12, N은 짝수) 가 불가사의하게 등장했습니다. 각각의 웜홀은 2D 좌표에서 다른 점에 존재합니다.

그의 계산에 따르면, 농부존은 그의 웜홀들이 N/2 개의 연결된 쌍을 만들 것이라는 걸 알고 있습니다. 이 쌍을 앞으로 "웜홀쌍" 이라고 부릅시다. 예를 들어, 웜홀 A와 B 가 쌍으로 연결된다면, 웜홀 A 를 통과하는 모든물체는 같은방향으로 움직이면서 웜홀 B 를 통해 나올 것입니다. 근데 좀 더 성가신 경우가 있습니다. 예를 들면, 웜홀 A 가 (0,0) 에 있고 B가(1,0) 에 있고, 베시가 (1/2,0)에서 시작해 +x 방향으로 움직인다고 가정해봅시다. 그러면 베시는 웜홀 B 로 들어갈 것이며 A 로 나올 것입니다. 그리고 다시 B 로 들어가고,...., 결국은 무한히 그 웜홀안에서 돌게 될 것입니다.

농부존은 웜홀의 모든 위치를 매우 정확하게 알고 있습니다. 또한 그는 베시가 +x 방향으로 움직이는 것을 좋아한다는 것을 알고 있습니다.(물론 그는 베시가 어디에 있는지는 정확하게 알지 못합니다.) 농부존을 도와 베시가 재수없는 위치에서 시작했을 때 무한 사이클에 빠질 수 있는 "웜홀짝"을 수 있는 경우의 수를 계산하시오.(이해 안가면 아래 예시 참조)

입력

* Line 1: 웜홀의 갯수 N이 주어집니다.. * Lines 2..1+N: 각각의 줄은 공백으로 구분된 웜홀의 좌표(x,y) 가 주어집니다.(0<=x,y<=1,000,000,000)

출력

* Line 1: 베시가 재수없는 위치에서 시작했을 때 무한 사이클에 빠질 수 있는 "웜홀짝"을 지을 수 있는 경우의 수를 계산하시오.

입출력 예 

입력 

4 
0 0 
1 0 
1 1 
0 1 

출력 

2 

INPUT DETAILS:  
위 예시에서는 4개의 웜홀이 각각 정사각형의 꼭짓점을 구성하는 모양으로 배치되어 있습니다..  

OUTPUT DETAILS:  
입력된 순서에 따라 1번~4번으로 숫자를 붙이고, 웜홀1-2를 하나로, 3-4를 하나로 묶었을 때 그가 (0,0) 과 (1,0) 사이 아무좌표에서 시작하거나 (0,1) 과 (1,1) 사이 아무좌표에서 시작했을 때 무한사이클에 걸릴 수 있습니다. 
비슷하게 위의 예시를 다르게 생각해보자면, 웜홀1과 3을 , 2와 4를 하나의 쌍으로 만들었을 때도 베시가 무한 사이클 함정에 빠질 수 있습니다. 웜홀1과4 , 2와3을 하나로 묶었을 때만이 베시가 +x  방향으로 진행할 때 베시가 어떠한 2D 좌표에서 시작하더라도 함정에 빠질수가 없습니다.
Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map of his farm.

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, if wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole B moving in the same direction, and any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences. For example, suppose there are two paired wormholes A at (0,0) and B at (1,0), and that Bessie the cow starts from position (1/2,0) moving in the +x direction. Bessie will enter wormhole B, exit from A, then enter B again, and so on, getting trapped in an infinite cycle!

Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow always walks in the +x direction, although he does not remember where Bessie is currently located. Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position.

입력

출력

* Line 1: The number of distinct pairings of wormholes such that Bessie could conceivably get stuck in a cycle walking from some starting point in the +x direction.

입출력 예

입력

4
0 0
1 0
1 1
0 1

출력

2
INPUT DETAILS:
There are 4 wormholes, forming the corners of a square.

OUTPUT DETAILS:
If we number the wormholes 1..4, then by pairing 1 with 2 and 3 with 4, Bessie can get stuck if she starts anywhere between (0,0) and (1,0) or between (0,1) and (1,1). Similarly, with the same starting points, Bessie can get stuck in a cycle if the pairings are 1-3 and 2-4. Only the pairings 1-4 and 2-3 allow Bessie to walk in the +x direction from any point in the 2D plane with no danger of cycling. 

출처:usaco/2013/dec/bronze
번역:conankun
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]