Problem 630: Crossed Lines

Mathematical Analysis

Pseudo-Random Point Generation

Points $P_i = (x_i, y_i)$ where $x_i = s_{2i}$, $y_i = s_{2i+1}$ from the recurrence:

Line Segments

From $T$ points, form segments $\overline{P_1 P_2}, \overline{P_3 P_4}, \ldots$ (pairing consecutive points).

Crossing Detection

Two segments $\overline{AB}$ and $\overline{CD}$ properly cross if and only if:

where $\text{ccw}(P,Q,R)$ denotes the orientation (counterclockwise) test:

Concrete Example

For the first few terms: $s_0 = 290797$, $s_1 = 290797^2 \bmod 50515093 = \ldots$

Derivation

Editorial

Generate points via pseudo-random sequence, form segments, count proper crossings using orientation tests. s_0 = 290797, s_{n+1} = s_n^2 mod 50515093. Method 1: Brute force O(n^2) pairwise crossing check Method 2: Sweep line (sketch). We generate** points from the recurrence. We then form** segments by pairing consecutive points. Finally, count crossings** by checking all pairs of segments.

Pseudocode

Generate** points from the recurrence
Form** segments by pairing consecutive points
Count crossings** by checking all pairs of segments

Brute Force: $O(n^2)$

Check all $\binom{S}{2}$ pairs of segments using the orientation test.

Sweep Line: $O((n+k)\log n)$

Bentley-Ottmann sweep line algorithm processes events (segment endpoints and intersection points) left-to-right, maintaining an ordered set of active segments.

Proof of Correctness

Theorem. Two segments $\overline{AB}$ and $\overline{CD}$ properly cross iff the orientation test (2) is satisfied.

Proof. Standard computational geometry result. The segments cross iff $A$ and $B$ are on opposite sides of line $CD$, and $C$ and $D$ are on opposite sides of line $AB$. The orientation test checks exactly this. $\square$

Complexity Analysis

• Brute force: $O(n^2)$ for $n$ segments.
• Sweep line: $O((n+k)\log n)$ for $k$ crossings.

Geometric Interpretation

The ccw function computes twice the signed area of triangle PQR. Positive = counterclockwise turn, negative = clockwise, zero = collinear.

Bentley-Ottmann Sweep Line

For n segments with k crossings: O((n+k) log n) by processing events left-to-right, maintaining an ordered set of active segments.

Integer Arithmetic

All coordinates are integers < 50515093. Products fit in 64-bit integers (max product ~ 2.5 x 10^15 < 2^63), avoiding floating-point errors.

Implementation Considerations

For the brute-force O(n^2) approach with n = 2500 segments: approximately 3.1 million pair checks, each O(1) using integer arithmetic. Total time: well under 1 second.

The pseudo-random sequence s_n has period dividing 50515092 (since the modulus 50515093 is prime). Points are uniformly distributed in [0, 50515092]^2. Collinearity probability is exactly zero for distinct coordinates.

The sweep-line approach (Bentley-Ottmann) becomes beneficial for n > 10000 with few crossings (k << n^2). It maintains a balanced BST of active segments ordered by y-coordinate at the sweep line position.

Degenerate Cases

For collinear points (ccw = 0), segments may overlap or touch at endpoints. These are not counted as proper crossings. With integer coordinates from a prime-modulus generator, degeneracies are extremely rare.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/*
 * Problem 630: Crossed Lines
 *
 * Generate points via s_{n+1} = s_n^2 mod 50515093, s_0 = 290797.
 * Form segments from consecutive point pairs.
 * Count proper crossings using orientation tests.
 */

ll ccw(ll ax, ll ay, ll bx, ll by, ll cx, ll cy) {
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

bool crosses(ll ax, ll ay, ll bx, ll by, ll cx, ll cy, ll dx, ll dy) {
    ll d1 = ccw(ax, ay, cx, cy, dx, dy);
    ll d2 = ccw(bx, by, cx, cy, dx, dy);
    ll d3 = ccw(ax, ay, bx, by, cx, cy);
    ll d4 = ccw(ax, ay, bx, by, dx, dy);
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
        return true;
    return false;
}

int main() {
    const ll MOD = 50515093;
    int n_points = 2500;  // adjust as needed

    // Generate points
    vector<ll> x(n_points), y(n_points);
    ll s = 290797;
    for (int i = 0; i < n_points; i++) {
        x[i] = s;
        s = s * s % MOD;
        y[i] = s;
        s = s * s % MOD;
    }

    // Form segments
    int n_seg = n_points / 2;
    ll count = 0;
    for (int i = 0; i < n_seg; i++) {
        for (int j = i + 1; j < n_seg; j++) {
            if (crosses(x[2*i], y[2*i], x[2*i+1], y[2*i+1],
                       x[2*j], y[2*j], x[2*j+1], y[2*j+1]))
                count++;
        }
    }
    cout << "Crossings: " << count << endl;
    return 0;
}

"""
Problem 630: Crossed Lines

Generate points via pseudo-random sequence, form segments,
count proper crossings using orientation tests.

s_0 = 290797, s_{n+1} = s_n^2 mod 50515093.

Method 1: Brute force O(n^2) pairwise crossing check
Method 2: Sweep line (sketch)
"""

def generate_points(n_points, s0=290797, mod=50515093):
    """Generate points from the pseudo-random sequence."""
    s = s0
    points = []
    for _ in range(n_points):
        x = s
        s = s * s % mod
        y = s
        s = s * s % mod
        points.append((x, y))
    return points

def ccw(A, B, C):
    """Orientation test: positive if counterclockwise."""
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])

def segments_cross(A, B, C, D):
    """Check if segments AB and CD properly cross."""
    d1 = ccw(A, C, D)
    d2 = ccw(B, C, D)
    d3 = ccw(A, B, C)
    d4 = ccw(A, B, D)
    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and \
       ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return True
    return False

def count_crossings(segments):
    """Count crossings between all pairs of segments."""
    n = len(segments)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            A, B = segments[i]
            C, D = segments[j]
            if segments_cross(A, B, C, D):
                count += 1
    return count

# Verify with small example
# Verify orientation test
assert ccw((0, 0), (1, 0), (0, 1)) > 0  # CCW
assert ccw((0, 0), (0, 1), (1, 0)) < 0  # CW

# Verify crossing
assert segments_cross((0, 0), (1, 1), (0, 1), (1, 0))  # X shape
assert not segments_cross((0, 0), (1, 0), (0, 1), (1, 1))  # parallel

# Generate points and segments
n_points = 20
points = generate_points(n_points)
segments = [(points[2*i], points[2*i+1]) for i in range(n_points // 2)]

crossings = count_crossings(segments)
print(f"Points: {n_points}, Segments: {len(segments)}, Crossings: {crossings}")
print("Verification passed.")