Intersections - MarisaOJ: Marisa Online Judge

Intersections

Time limit: 1000 ms
Memory limit: 256 MB
You are given $n$ line segments on a 2D coordinate grid. Each segment is either horizontal (parallel to the x-axis) or vertical (parallel to the y-axis). For each pair of segments $(i, j)$ with $1 \le i \le j \le n$, define $f(i, j)$ as the number of integer coordinate intersection points between segment $i$ and segment $j$. Your task is to compute the total sum of all $f(i, j)$. Two segments might have multiple intersection points. One point might be the intersection points of multiple pairs of segments. ### 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_1)$ and $(x_2,y_2)$. ### Output - Print a single integer: the total number of integer coordinate intersections among all pairs of segments. ### Constraints - $1 \le n \le 2 \times 10^5$ - $1 \le x_1, y_1, x_2, y_2 \le 10^5$ ### Example Input: ``` 4 2 2 1 2 2 2 2 1 2 2 3 2 2 2 4 2 ``` Output: ``` 7 ```