회사는 아주 높은 두 건물에 위치해 있습니다. 회사 인트라넷은 많은 회선으로 건물을 연결하는데, 각 회선은 첫 번째 건물 창문과 두 번째 건물 창문을 연결합니다.
한쪽 건물이 왼쪽에 오고 또 다른 건물이 오른쪽에 오게 건물을 측면에서 바라봅시다. 왼쪽 건물의 창문은 건물 오른쪽 벽의 점으로 나타낼 수 있고, 오른쪽 건물의 창문은 건물 왼쪽 벽의 점으로 나타낼 수 있습니다. 회선은 왼쪽 건물의 창문과 오른쪽 건물의 창문을 연결하는 직선 부분입니다.
(그림 참조)
당신은 그 어떤 회선도 끝 점을 공유하지 않는다는 (즉, 각 창문에서 나가는 회선이 최대 하나라는) 것을 발견했습니다. 하지만 당신의 시점에서, 몇몇 회선은 중간에서 교차합니다. 이때 당신은 각 교차점에서 정확히 두 개의 회선만 교차한다는 것 역시 발견했습니다.
위 그림에서, 교차점은 검은색 원, 창문은 흰색 원으로 표시했습니다.
당신은 몇 개의 교차점을 확인할 수 있습니까?
입력
첫 줄에 테스트 케이스의 수 T가 주어집니다. T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 회선의 수를 나타내는 하나의 정수 N이 한 줄에 주어지며 시작됩니다.
다음 N개의 줄은 Ai와 Bi로 각각 하나의 회선을 설명합니다. 이는 회선이 연결하는 창문에 대한 설명입니다: Ai는 회선이 연결하는 왼쪽 건물 창문의 높이, Bi는 회선이 연결하는 오른쪽 건물 창문의 높이입니다.
제한
- 1 <= T <= 15
- 1 <= Ai <= 10 ^ 4
- 1 <= Bi <= 10 ^ 4
- 각 테스트 케이스에 대해, 모든 Ai는 서로 다릅니다.
- 각 테스트 케이스에 대해, 모든 Bi는 서로 다릅니다.
- 세 개 이상의 회선이 한 점에서 교차하는 경우는 없습니다.
- 1 <= N <= 2
출력
각 테스트 케이스에 대해, x가 (1부터 시작하는) 테스트 케이스 번호를 나타내고 y가 교차하는 점의 수를 나타내는 "Case #x: y"를 출력합니다.
ez_code 4년 전 7
문제
회사는 아주 높은 두 건물에 위치해 있습니다. 회사 인트라넷은 많은 회선으로 건물을 연결하는데, 각 회선은 첫 번째 건물 창문과 두 번째 건물 창문을 연결합니다.
한쪽 건물이 왼쪽에 오고 또 다른 건물이 오른쪽에 오게 건물을 측면에서 바라봅시다. 왼쪽 건물의 창문은 건물 오른쪽 벽의 점으로 나타낼 수 있고, 오른쪽 건물의 창문은 건물 왼쪽 벽의 점으로 나타낼 수 있습니다. 회선은 왼쪽 건물의 창문과 오른쪽 건물의 창문을 연결하는 직선 부분입니다.
(그림 참조)
당신은 그 어떤 회선도 끝 점을 공유하지 않는다는 (즉, 각 창문에서 나가는 회선이 최대 하나라는) 것을 발견했습니다. 하지만 당신의 시점에서, 몇몇 회선은 중간에서 교차합니다. 이때 당신은 각 교차점에서 정확히 두 개의 회선만 교차한다는 것 역시 발견했습니다.
위 그림에서, 교차점은 검은색 원, 창문은 흰색 원으로 표시했습니다.
당신은 몇 개의 교차점을 확인할 수 있습니까?
입력
첫 줄에 테스트 케이스의 수 T가 주어집니다. T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 회선의 수를 나타내는 하나의 정수 N이 한 줄에 주어지며 시작됩니다.
다음 N개의 줄은 Ai와 Bi로 각각 하나의 회선을 설명합니다. 이는 회선이 연결하는 창문에 대한 설명입니다: Ai는 회선이 연결하는 왼쪽 건물 창문의 높이, Bi는 회선이 연결하는 오른쪽 건물 창문의 높이입니다.
제한
- 1 <= T <= 15
- 1 <= Ai <= 10 ^ 4
- 1 <= Bi <= 10 ^ 4
- 각 테스트 케이스에 대해, 모든 Ai는 서로 다릅니다.
- 각 테스트 케이스에 대해, 모든 Bi는 서로 다릅니다.
- 세 개 이상의 회선이 한 점에서 교차하는 경우는 없습니다.
- 1 <= N <= 2
출력
각 테스트 케이스에 대해, x가 (1부터 시작하는) 테스트 케이스 번호를 나타내고 y가 교차하는 점의 수를 나타내는 "Case #x: y"를 출력합니다.