시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 2 | 2 | 100.000% |
Dreamoon likes algorithm competitions very much. But when he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segments on his calculation paper.
Dreamoon's calculation paper is special: it can be imagined as the plane with Cartesian coordinate system with range $[0, 2000] \times [0, 2000]$ for the coordinates. The grid lines are all lines of the form $x = c$ or $y = c$ for every integer $c$ between $0$ and $2000$, inclusive. So, the grid contains $2000 \times 2000$ squares.
Now, Dreamoon wonders how many grid squares are crossed by at least one of the lines he drew. Please help Dreamoon find the answer. Note that touching an edge of a grid square is not considered as crossing this square.
The first line of input contains an integer $N$ denoting the number of lines Dreamoon draw. The $i$-th line of following $N$ lines contains four integers $x_{i1}, y_{i1}, x_{i2}, y_{i2}$, denoting that the $i$-th segment Dreamoon drew is a straight line segment between points $(x_{i1}, y_{i1})$ and $(x_{i2}, y_{i2})$.
Output one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.
3 0 0 5 5 0 5 5 0 0 5 5 0
9
1 0 0 4 3
6
2 0 0 4 3 1 0 3 3
6