moner_ari   1년 전

[문제]

한 회사가 아주 높은 두 건물에 있습니다. 두 건물을 연결하는 회사의 인트라넷은 많은 와이어로 연결이 되어 있는데, 각 와이어는 1번째 건물의 창문과 2번째 건물의 창문을 연결합니다.

여러분은 이들 건물을 옆에서 바라보고 있기에, 한 건물은 왼쪽에 있고 다른 건물은 오른쪽에 있는 것으로 보입니다. 왼쪽 건물의 창문은 그 건물 오른쪽 벽의 점으로 보이며, 오른쪽 건물의 창문도 그 건물 왼쪽 벽의 점으로 보입니다. 와이어는 왼쪽 건물의 창문과 오른쪽 건물의 창문을 연결하는 직선입니다.

<그림> - 문제 본문 참조.

여러분은 어떠한 두 와이어도 같은 점에 겹치지 않는다는 것을 알아냈습니다. (즉, 각 창문에는 와이어가 최대 1개만 있습니다.) 하지만, 여러분이 바라볼 때, 일부 와이어는 중간에 만나기도 합니다. 여러분은 정확히 2개의 와이어가 각 교차점에서 만난다는 것도 알아냈습니다.

위 그림에서, 교차점은 검은색 원으로, 창문은 흰색 원으로 나타냈습니다.

여러분이 볼 수 있는 교차점은 몇 개인가요?

--------

[입력]

첫 번째 줄에는 테스트 케이스의 개수 T가 주어지며, 입력은 T개의 테스트 케이스로 주어집니다. 각 테스트 케이스는 여러분이 볼 수 있는 와이어의 개수인, 정수 N이 주어진 줄로 시작합니다.

다음 N개의 줄에서 각 와이어의 정보가 2개의 정수 Ai와 Bi로 주어집니다. Ai와 Bi는 해당 와이어가 연결하는 창문을 의미합니다. 즉, Ai는 왼쪽 건물의 창문의 높이를, Bi는 오른쪽 건물의 창문의 높이를 의미합니다.

--------

[제한]

  • 1 ≤ T ≤ 15.
  • 1 ≤ Ai ≤ 104.
  • 1 ≤ Bi ≤ 104.
  • 각 테스트 케이스에서, 모든 Ai의 값은 다릅니다.
  • 각 테스트 케이스에서, 모든 Bi의 값은 다릅니다.
  • 어떠한 세 와이어도 같은 점에서 교차하지 않습니다.
  • 1 ≤ N ≤ 1000.

--------

[출력]

각 테스트 케이스마다, "Case #x: y"를 출력합니다. 여기서 x는 테스트 케이스의 번호로 1에서 시작하며, y는 여러분이 볼 수 있는 교차점의 개수입니다.

댓글을 작성하려면 로그인해야 합니다.