CF 102388B - Stars

A star exists at every point whose two coordinates are integers. For each test case, we are given the two endpoints of a straight line segment, and we need to count every integer-coordinate point that lies on that segment, including both endpoints.

codeforcescompetitive-programming

CF 102388B - Stars

Rating: -
Tags: -
Solve time: 1m 47s
Verified: no

Solution

Problem Understanding

A star exists at every point whose two coordinates are integers. For each test case, we are given the two endpoints of a straight line segment, and we need to count every integer-coordinate point that lies on that segment, including both endpoints.

The coordinates can be as large as (10^9) in either direction. Consequently, the difference between two endpoint coordinates can reach (2\cdot10^9). A solution that visits every possible coordinate along the segment can therefore require around two billion iterations for just one test case. Since there can be up to 100 test cases and the time limit is only one second, the intended solution must do a constant amount of arithmetic per test case rather than depend on the geometric length of the segment.

There are several cases where a direct formula can easily go wrong. If both endpoints are identical, for example

1
5 -3 5 -3

the answer is 1, because the segment consists of one star. A formula such as gcd(dx, dy) without the final +1 would incorrectly return zero.

A horizontal segment is another useful boundary case:

1
2 7 6 7

The covered stars are ((2,7),(3,7),(4,7),(5,7),(6,7)), so the answer is 5. The vertical case behaves identically. A careless implementation that divides by the slope can run into division by zero, even though the number of lattice points is perfectly well defined.

Negative coordinates also require no special geometric treatment. For

1
-2 -2 2 2

the lattice points are ((-2,-2),(-1,-1),(0,0),(1,1),(2,2)), giving 5. The differences may be negative, so the greatest common divisor must be computed from their absolute values.

Finally, a segment can have a very large coordinate difference but contain only its two endpoints. For example,

1
0 0 1000000000 1

has answer 2, because the coordinate changes have gcd (1). A solution based on segment length would completely miss this distinction.

Approaches

The most direct approach is to enumerate integer-coordinate candidates along the segment. For example, if the endpoints have different (x)-coordinates, we can inspect every integer (x) between them, determine the corresponding point on the line, and count it when its (y)-coordinate is also an integer. This is correct because every lattice point on a non-vertical segment has exactly one integer (x)-coordinate, so every possible lattice point is considered.

The problem is the number of iterations. A segment from ((-10^9,-10^9)) to ((10^9,10^9)) contains (2\cdot10^9+1) lattice points, and a coordinate-by-coordinate scan can require roughly two billion iterations for that single test case. With 100 test cases, the worst case reaches about (2\cdot10^{11}) iterations, far beyond the one-second limit.

The key observation is that lattice points on a segment are evenly spaced in integer coordinate steps. Let

[ dx = x_1-x_0,\qquad dy=y_1-y_0. ]

Suppose a lattice point is reached from the first endpoint by moving (k) identical integer steps. The step must have the form

[ \left(\frac{dx}{g},\frac{dy}{g}\right), ]

where

[ g=\gcd(|dx|,|dy|). ]

This is the smallest integer step that still reaches the other endpoint. Starting at the first endpoint, we can take exactly (g) such steps to arrive at the second endpoint. The number of visited points is consequently (g+1), because the starting point is also a star.

For example, from ((1,2)) to ((3,6)), the coordinate difference is ((2,4)). Their gcd is (2), so the primitive step is ((1,2)). The points are ((1,2)), ((2,4)), and ((3,6)), giving (2+1=3).

The brute-force method works because it explicitly searches for these integer points, but fails when the coordinate range is enormous. The observation that all valid lattice points are generated by repeatedly applying the smallest integer step reduces the entire problem to one gcd computation.

Approach Time Complexity Space Complexity Verdict
Brute Force (O(\max( dx ,
Optimal (O(\log(\max( dx ,

Algorithm Walkthrough

  1. Read the two endpoints ((x_0,y_0)) and ((x_1,y_1)), then compute (dx=x_1-x_0) and (dy=y_1-y_0). These differences completely describe how far the segment moves horizontally and vertically.
  2. Take the absolute values of both differences and compute (g=\gcd(|dx|,|dy|)). The gcd tells us how many equal integer-coordinate steps fit exactly into the total displacement.
  3. Return (g+1). There are (g) intervals between consecutive lattice points, and a sequence of (g) intervals contains (g+1) endpoints.
  4. If both endpoints coincide, then (dx=dy=0), and (\gcd(0,0)) is treated as (0) by Python's math.gcd. The formula still gives (0+1=1), which is exactly the desired answer.

Why it works

Let (g=\gcd(|dx|,|dy|)). Since (g) divides both coordinate differences, the vector

[ \left(\frac{dx}{g},\frac{dy}{g}\right) ]

has integer coordinates. Repeating this vector (k) times from the first endpoint gives

[ \left(x_0+k\frac{dx}{g},\ y_0+k\frac{dy}{g}\right) ]

for every integer (k) from (0) through (g), so there are at least (g+1) lattice points on the segment.

The step is primitive because the two components after division by (g) are coprime. A smaller positive step with integer coordinates cannot move along the same line and still reach the endpoint exactly. Thus there are no additional lattice points between consecutive generated points. The complete set of lattice points is exactly the (g+1) points obtained for (k=0,1,\ldots,g), proving that the answer is (\gcd(|dx|,|dy|)+1).

Python Solution

import sys
from math import gcd

input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []

    for _ in range(t):
        x0, y0, x1, y1 = map(int, input().split())

        dx = abs(x1 - x0)
        dy = abs(y1 - y0)

        ans.append(str(gcd(dx, dy) + 1))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    solve()

The code first reads the number of segments and stores each answer as a string so that all output can be written at once. This keeps input and output overhead small, although the actual computation is already extremely fast.

For each segment, the absolute coordinate differences are computed before calling gcd. The signs of the differences determine the direction of the segment but do not affect how many lattice points lie on it.

Using gcd(dx, dy) + 1 also handles horizontal, vertical, and zero-length segments without separate branches. For a horizontal segment, dy is zero and the gcd becomes dx. For a vertical segment, the same happens with dx equal to zero. For identical endpoints, both arguments are zero and Python returns gcd(0, 0) = 0.

Python integers have arbitrary precision, so the coordinate differences up to (2\cdot10^9) and the resulting answer up to (2\cdot10^9+1) require no overflow handling. In languages with fixed-width integer types, a 64-bit integer is more than sufficient.

The +1 is applied only after the gcd is computed. The gcd counts the number of equal steps between lattice points, while the requested quantity counts the points themselves, so the number of points is one greater than the number of steps.

Worked Examples

The first sample contains a zero-length segment. For the input 1 1 1 1, the differences are both zero.

(x_0) (y_0) (x_1) (y_1) (dx) (dy) gcd Answer
1 1 1 1 0 0 0 1

The gcd is zero because there is no displacement at all. The segment still contains its single endpoint, so adding one gives the correct result.

For the sample segment from ((1,2)) to ((3,6)), the coordinate changes are (2) and (4). Their gcd is (2), meaning the segment can be divided into two equal primitive steps.

(x_0) (y_0) (x_1) (y_1) (dx) (dy) gcd Primitive step Answer
1 2 3 6 2 4 2 ((1,2)) 3

Starting at ((1,2)), one primitive step reaches ((2,4)), and another reaches ((3,6)). The three resulting stars agree with the formula (2+1=3).

The third sample, ((-1,-1)) to ((50,101)), demonstrates that the signs of the coordinates do not matter.

(x_0) (y_0) (x_1) (y_1) (dx) (dy) gcd Answer
-1 -1 50 101 51 102 51 52

The primitive step is ((1,2)), so there are 51 equal intervals and 52 lattice points. Taking absolute differences lets the same calculation work regardless of the direction of the segment.

Complexity Analysis

Measure Complexity Explanation
Time (O(T\log C)) Each test case performs one Euclidean gcd computation on values at most (2\cdot10^9), where (C) is the maximum coordinate difference.
Space (O(T)) The implementation stores the output strings before writing them.

With (T\le100), the algorithm performs only a few thousand arithmetic operations in the worst case. The coordinate range affects the logarithmic gcd computation rather than causing a scan proportional to the segment length, so the solution is comfortably within the one-second time limit and uses negligible memory compared with the 256 MB limit.

Test Cases

import sys
import io
from math import gcd

def solve():
    input = sys.stdin.readline
    t = int(input())
    ans = []

    for _ in range(t):
        x0, y0, x1, y1 = map(int, input().split())
        ans.append(str(gcd(abs(x1 - x0), abs(y1 - y0)) + 1))

    sys.stdout.write("\n".join(ans))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided sample
assert run("""\
4
1 1 1 1
1 2 3 6
-1 -1 50 101
-10000 1 1000000000 0
""") == """\
1
3
52
2
""", "sample"

# Minimum-size and all-equal coordinates
assert run("""\
1
0 0 0 0
""") == "1\n", "zero-length segment"

# Horizontal and vertical segments
assert run("""\
2
2 7 6 7
-3 -5 -3 4
""") == """\
5
10
""", "horizontal and vertical segments"

# gcd = 1, despite a very large coordinate difference
assert run("""\
1
0 0 1000000000 1
""") == "2\n", "only endpoints are lattice points"

# Maximum possible displacement in both coordinates
assert run("""\
1
-1000000000 -1000000000 1000000000 1000000000
""") == "2000000001\n", "maximum-size diagonal"

# Negative direction and a nontrivial gcd
assert run("""\
1
10 10 -2 -2
""") == "7\n", "negative coordinate direction"
Test input Expected output What it validates
0 0 0 0 1 Zero-length segment and gcd(0, 0).
2 7 6 7 5 Horizontal segment and the endpoint count.
-3 -5 -3 4 10 Vertical segment with negative coordinates.
0 0 1000000000 1 2 Large range with gcd equal to one, catching length-based mistakes.
-1000000000 -1000000000 1000000000 1000000000 2000000001 Maximum coordinate differences and large answer.
10 10 -2 -2 7 Negative direction and a gcd greater than one.

Edge Cases

For a zero-length segment such as

1
5 -3 5 -3

the algorithm computes (dx=0) and (dy=0). Python's gcd returns zero, so the final value is (0+1=1). The single endpoint is exactly one lattice point, so there is no special case needed in the implementation.

For a horizontal segment such as

1
2 7 6 7

the differences are (dx=4) and (dy=0). The gcd is (4), and the answer is (5). The primitive step is ((1,0)), producing the five stars from (x=2) through (x=6). A vertical segment works through the same calculation with the roles of (x) and (y) exchanged.

For a segment whose endpoints have a huge coordinate difference but whose coordinate differences are coprime,

1
0 0 1000000000 1

the gcd is (1), so the answer is (2). The only lattice points are the two endpoints. This case demonstrates why the number of lattice points depends on the gcd of the coordinate differences, not on the Euclidean length or the magnitude of either coordinate difference alone.

For negative coordinates and reversed direction,

1
10 10 -2 -2

the raw differences are (-12) and (-12), but their absolute values have gcd (12). The algorithm returns (13), corresponding to the points ((10,10),(9,9),\ldots,(-2,-2)). Taking absolute values before the gcd removes direction from the calculation while preserving the number of lattice steps.

For the maximum-size diagonal,

1
-1000000000 -1000000000 1000000000 1000000000

both coordinate differences have absolute value (2\cdot10^9). Their gcd is also (2\cdot10^9), so the answer is (2\cdot10^9+1=2000000001). The result is large, but it is still obtained with a single gcd computation rather than billions of iterations.