Overlapping Line Segments

Time limit2sMemory limit256 MB

Summary
Count unordered pairs among up to 100,000 line segments that overlap in more than a single point.
Level

Medium7 of 10

Topics
Geometry, Sorting, Math
Solved
No attempts yet

Problem

You are given N line segments. Two segments are considered overlapping if they share a portion with positive length, not just one point. Equivalently, the set of points contained in both segments must be infinite. If only their endpoints touch, they are not overlapping.

Count the number of unordered pairs of distinct segments that overlap.

N is between 1 and 100,000 inclusive.

Input

The first line contains the integer N. Each of the next N lines contains four integers x1 y1 x2 y2, the coordinates of the two endpoints of one segment.

Every coordinate is an integer between 0 and 1,000,000 inclusive. The two endpoints of a segment are never the same point.

Output

Print the number of unordered pairs of distinct segments that overlap.

Examples1

  1. Example 1

    Input
    3
1 1 2 2
2 2 3 3
1 1 3 3
    Expected output
    2