We are given a circle in the plane and a set of n line segments, such that every segment endpoint lies on the circle. Assume that no two segments share a common endpoint. The goal is to write a program for computing the number of pairs of these segments that intersect.

Let us assume that the 2n segment endpoints are labeled 1, 2, ..., 2n in clockwise order around the circle. A segment is specified as a pair (i, j), where i and j are one of the 2n labels.

The input data is given in a file whose first line specifies n, the number of segments. Each of the subsequent n lines of the file identifies one of the n segments, which is specified by a pair of labels separated by space characters. For, example, suppose n = 5, and the segments are (10, 8), (1,7), (2,5), (3,6), and (4,9).

In this example, five pairs of segments intersect. The segment (4,9) intersects with the four other segments; furthermore segments (2,5) and (3, 6) intersect. The intersections are clear if one looks at a geometric visualization.

Write a program in Python that asks for an input file that contains the data in the above format, and outputs the number of segment pairs that intersect. The goal is to make the program run as fast as possible. The baseline is the straightforward algorithm that checks each pair of segments for a possible intersection. Your program should certainly be significantly faster than that. Your program should be sequential, that is, it should not resort to any kind of parallelism like threads, GPU, etc. We want to keep the focus on algorithmic ideas in the sequential setting.

Please submit your program, instructions for running it, a description of your algorithm ideas and the actual running time on certain input files(with n up to a 100,000).

Sample Input file: SizeA.txt

10 1 6 2 3 4 10 5 11 7 12 8 16 9 13 14 19 15 17 18 20