Intersections - MarisaOJ: Marisa Online Judge

Intersections

Time limit: 1000 ms
Memory limit: 256 MB
Count the number of intersections between $n$ line segments on a two-dimensional coordinate grid. All line segments are parallel to either the x-axis or the y-axis. Two segments may have more than one intersections. ### Input - The first line contains an integer $n$. - The next $n$ lines each contain four integers $x_1, y_1, x_2, y_2$ representing a line segment with endpoints $(x_1, y_2)$ and $(x_2, y_2)$. ### Output - Print an integer representing the number of intersections. ### Constraints - $1 \leq n \leq 2 \times 10^5$. - $1 \leq x_1, y_1, x_2, y_2 \leq 10^5$. ### Example Input: ``` 4 1 2 4 2 2 3 2 1 4 1 4 4 1 4 2 4 ``` Output: ``` 2 ```