@@ -0,0 +1,2304 @@
+#!/usr/bin/python -tt%0A%0A%22%22%22Solves Google Code Jam 2010 Round 1C Problem A%0A(https://code.google.com/codejam/contest/619102/dashboard#s=p0)%0A%22Rope Intranet%22%0A%22%22%22%0A%0Aimport sys%0A%0A%0Adef read_input():%0A    %22%22%22Parses problem data from stdin.%0A%0A    Args:%0A        None%0A%0A    Returns:%0A        List of test cases, each of which is list of tuples of wire data%0A        (height_on_side_a, height_on_side_b)%0A    %22%22%22%0A%0A    lines = sys.stdin.read().splitlines()%0A    num_test_cases = int(lines%5B0%5D)%0A    test_cases = %5B%5D%0A    i = 1%0A    for _ in range(num_test_cases):%0A        wires = %5B%5D%0A        num_wires = int(lines%5Bi%5D)%0A        i += 1%0A        for _ in range(num_wires):%0A            # map() ungood :(%0A            #(height_a, height_b) = map(int, lines%5Bi%5D.split())%0A            (height_a, height_b) = %5Bint(x) for x in lines%5Bi%5D.split()%5D%0A            wires.append((height_a, height_b))%0A            i += 1%0A        test_cases.append(wires)%0A    return test_cases%0A%0A%0Adef solve(wires):%0A    %22%22%22Calculates number of intersections given list of wires.%0A%0A    Args:%0A        List of tuples of wire data (height_on_side_a, height_on_side_b)%0A%0A    Returns:%0A        Integer representing total number of wire intersections given specified%0A        wire data%0A    %22%22%22%0A%0A    # Approach: if there's an algorithm faster than O(n%5E2), it doesn't occur to%0A    # me at the moment; so, we'll check all n-choose-2 wire combinations:%0A    # repeatedly remove a wire from the list and test it for intersection with%0A    # all wires remaining in the list%0A    num_intersections = 0%0A    while wires:%0A        wire = wires.pop()%0A        for wire_other in wires:%0A            # wires cross if their points don't have the same relationship on%0A            # both sides, with respect to which is higher; i.e. if wire A's%0A            # attachment points are both higher or both lower than wire B's,%0A            # A and B don't cross%0A            if ((wire%5B0%5D %3C wire_other%5B0%5D and wire%5B1%5D %3E wire_other%5B1%5D) or%0A                (wire%5B0%5D %3E wire_other%5B0%5D and wire%5B1%5D %3C wire_other%5B1%5D)):%0A                num_intersections += 1%0A    return num_intersections%0A%0A%0Adef main():%0A    test_cases = read_input()%0A    i = 1%0A    for test_case in test_cases:%0A        num_intersections = solve(test_case)%0A        print 'Case #%25d: %25d' %25 (i, num_intersections)%0A        i += 1%0A%0A%0Aif __name__ == '__main__':%0A    main()%0A

Create rope_intranet.py