# Counting intersections of wires between towers

The "Rope Intranet" problem from Google Codejam 2010 asks us to count the number of intersections (black circles) in a planar straight-line graph like this: That is, with each line segment having one endpoint with $x=x_0$ and the other with $x=x_1$.

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each case begins with a line containing an integer $N$, denoting the number of wires you see.

The next $N$ lines each describe one wire with two integers $A_i$ and $B_i$. These describe the windows that this wire connects: $A_i$ is the height of the window on the left building, and $B_i$ is the height of the window on the right building.

Output

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the case number (starting from 1) and $y$ is the number of intersection points you see.

Sample input

2
3
1 10
5 5
7 7
2
1 1
2 2


Sample output

Case #1: 2
Case #2: 0


I have a working solution, but the time complexity is awful. Here is my code:

def solve(wire_ints, test_case):
for iterI in range(number_wires):
for iterJ in range(iterI):
holder = [wire_ints[iterI], wire_ints[iterJ]]
holder.sort()
if holder > holder:
return("Case #" + str(test_case) + ":" + " " + str(answer_integer))

for test_case in range(1, int(input()) + 1):
number_wires = int(input())
wire_ints = []
for count1 in range(number_wires):
left_port,right_port = map(int, input().split())
wire_ints.append((left_port,right_port))

The first (which you spotted), is that the exact heights of the left and right endpoints of each line segment don't matter, only their order. That is, a line $A_i, B_i$ intersects the line $A_j, B_j$ if either $A_i < A_j$ and $B_i > B_j$, or $A_i > A_j$ and $B_i < B_j$.
The second, is that each pair of intersecting lines is an "inversion". (An inversion is a pair of items that are out of order with respect to a permutation.) That is, if we start with the lines in order of their left heights $A_i$, and consider sorting them into the order of their right heights $B_i$, the number of intersections is the same as the number of inversions with respect to the sorted order.
The number of inversions in a sequence with respect to a sorted order can be counted in $O(n \log n)$ using an adaptation of the merge sort algorithm. This is a standard exercise in an algorithms course (for example, it's exercise 2–4d in Introduction To Algorithms by Cormen, Leiserson, Rivest, and Stein), so I won't spoil it for you here.