Crossing Segments

Difficulty: 1700 6000 ms 128 MB

geometry

Count the pairs of line segments that intersect (touching at an endpoint or overlapping counts as intersecting).

Input: the first line has N; each of the next N lines has a segment x1 y1 x2 y2.

Output: the number of intersecting pairs.

Constraints:

• 1 ≤ N ≤ 10³
• |coordinates| ≤ 10⁴

Sample Tests

3
0 0 4 4
0 4 4 0
5 5 6 6

1

2
0 0 1 1
2 2 3 3

0

Read the Editorial