Segments
You are given N line segments in a plane (N <= 1000). For each of the line segments you know the coordinates of the endpoints, with all the coordinates being between 0 and 1000000. You have to find out how many different points with integers coordinates lies on one of the line segments.
If a points lies on more than one line segment, we count it only once!
InputFrom the first line of the standard input read the number N, and from each of the next N lines read four numbers: ( X1i , Y1i ), ( X2i , Y2i ) that represent the coordinates of the i-th line segment.
There will be no test case in which coordinates of the two end points, of the same line segment, are the same.
There will be no test case in which coordinates of the two end points, of the same line segment, are the same.
OutputTo the standard output write one integer representing the number of points with integer coordinates that the line segments contain.
Input:
Output:
4
2 1 6 3
6 1 6 5
2 1 5 7
5 1 2 4Output:
12Image: example1
Explanation:
The points with integer coordinates that belong to at least one of the line segments are: (2, 1), (5, 1), (6, 1), (4, 2), (6, 2), (3, 3), (6, 3), (2, 4), (6, 4), (4, 5), (6, 5), (5, 7).
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.