Problem 630: Crossed Lines
View on Project EulerProject Euler Problem 630 Solution
EulerSolve provides an optimized solution for Project Euler Problem 630, Crossed Lines, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary The problem defines a deterministic pseudo-random sequence, uses it to generate \(n\) lattice points in the square \([-1000,999]^2\), and then forms a geometric line from every unordered pair of distinct points. Let \(M\) be the number of distinct lines that appear. For each distinct line \(L\), count how many other distinct lines cross it, and sum those counts over all \(L\). That total is \(S\), which is equivalently the number of ordered pairs of distinct non-parallel lines. The task is to compute \(S\) for \(n=2500\). Mathematical Approach The solution has two parts: represent every geometric line in a unique integer form, then count how many of those distinct lines share the same slope. Step 1: Generate the deterministic point set The points come from the recurrence $$S_0=290797,\qquad S_{k+1}=S_k^2 \bmod 50515093,$$ followed by $$T_k=(S_k \bmod 2000)-1000,\qquad P_n=(T_{2n-1},T_{2n}).$$ So every point has integer coordinates in \([-1000,999]\). The sequence is completely deterministic, which means every implementation works with exactly the same input set. Step 2: Represent every geometric line canonically Take two distinct points \((x_1,y_1)\) and \((x_2,y_2)\)....
Detailed mathematical approach
Problem Summary
The problem defines a deterministic pseudo-random sequence, uses it to generate \(n\) lattice points in the square \([-1000,999]^2\), and then forms a geometric line from every unordered pair of distinct points. Let \(M\) be the number of distinct lines that appear. For each distinct line \(L\), count how many other distinct lines cross it, and sum those counts over all \(L\). That total is \(S\), which is equivalently the number of ordered pairs of distinct non-parallel lines. The task is to compute \(S\) for \(n=2500\).
Mathematical Approach
The solution has two parts: represent every geometric line in a unique integer form, then count how many of those distinct lines share the same slope.
Step 1: Generate the deterministic point set
The points come from the recurrence
$$S_0=290797,\qquad S_{k+1}=S_k^2 \bmod 50515093,$$
followed by
$$T_k=(S_k \bmod 2000)-1000,\qquad P_n=(T_{2n-1},T_{2n}).$$
So every point has integer coordinates in \([-1000,999]\). The sequence is completely deterministic, which means every implementation works with exactly the same input set.
Step 2: Represent every geometric line canonically
Take two distinct points \((x_1,y_1)\) and \((x_2,y_2)\). Write
$$\Delta x=x_2-x_1,\qquad \Delta y=y_2-y_1,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
After dividing by \(g\), the primitive direction vector is
$$u=\frac{\Delta x}{g},\qquad v=\frac{\Delta y}{g}.$$
A primitive normal vector is then
$$A=v,\qquad B=-u,$$
and the line can be written as
$$Ax+By=C,\qquad C=Ax_1+By_1.$$
To make this representation unique, multiply \((A,B,C)\) by \(-1\) whenever \(A \lt 0\), or when \(A=0\) and \(B \lt 0\). After that sign rule, one geometric line corresponds to exactly one normalized triple \((A,B,C)\). Vertical and horizontal lines are handled automatically by the same formula.
Step 3: Count distinct lines
There are
$$P=\binom{n}{2}$$
unordered point pairs. Each pair produces one candidate line key, except coincident points, which are ignored because they do not determine a unique line. If three or more points are collinear, several different pairs produce the same normalized triple. Let \(\mathcal{L}\) be the set of distinct normalized triples after deduplication. Then
$$M=\lvert\mathcal{L}\rvert.$$
Step 4: Group parallel classes and derive the crossing formula
Two distinct normalized lines are parallel exactly when they have the same normalized normal vector \((A,B)\). Let the parallel classes have sizes
$$m_1,m_2,\dots,m_r,\qquad m_1+\cdots+m_r=M.$$
The number of ordered pairs of distinct lines is
$$M(M-1).$$
Within a single class of size \(m_t\), the ordered parallel pairs number
$$m_t(m_t-1).$$
Once duplicate lines have already been merged, any two distinct non-parallel lines intersect exactly once in the Euclidean plane. Hence the required total is
$$\boxed{S=M(M-1)-\sum_{t=1}^{r} m_t(m_t-1).}$$
Step 5: Worked example with the first three generated points
The first three generated points are
$$P_1=(527,144),\qquad P_2=(-488,732),\qquad P_3=(-454,-947).$$
The three normalized lines are
$$L_{12}: 84x+145y=65148,$$
$$L_{13}: 1091x-981y=433693,$$
$$L_{23}: 1679x+34y=-794464.$$
All three triples are different, and no two of them share the same \((A,B)\). So every parallel class has size \(1\), which gives
$$M=3,\qquad S=3\cdot 2-0=6.$$
This is the smallest benchmark used by the implementation, and it confirms that the ordered-pair interpretation is the correct one.
How the Code Works
The C++, Python, and Java implementations all follow the same mathematical pipeline. They generate the point sequence, iterate over every pair \(i<j\), compute the normalized line coefficients, and collect those line keys. The Python implementation stores tuple keys in a set and sorts the distinct set afterward, while the C++ and Java implementations store compact integer keys so the full list can be sorted directly and deduplicated efficiently.
After sorting, consecutive equal keys are merged to obtain \(M\). A second linear scan groups consecutive lines by their slope part \((A,B)\). If one group contains \(m\) distinct lines, the implementation adds \(m(m-1)\) to the total number of ordered parallel pairs. Subtracting that sum from \(M(M-1)\) yields the final answer.
The compiled implementation also includes deterministic sanity checks: it confirms the first three generated points and verifies the benchmark values \(M=4948\) and \(S=24477690\) for the first \(100\) generated points before evaluating the full case \(n=2500\).
Complexity Analysis
Let \(P=\binom{n}{2}\). Generating all candidate lines takes \(O(P)\) arithmetic operations, and the gcd inputs are bounded because all coordinates stay inside a fixed box. Sorting dominates the runtime, so the total time is \(O(P\log P)\), which is \(O(n^2\log n)\). The memory usage is \(O(P)\), since the algorithm stores one key per point pair before deduplication.
Footnotes and References
- Problem page: https://projecteuler.net/problem=630
- Line (geometry): Wikipedia — Line (geometry)
- Greatest common divisor: Wikipedia — Greatest common divisor
- Finding the equation of a line from two points: cp-algorithms — Finding the equation of a line for a segment
- Line arrangement: Wikipedia — Line arrangement
Problem 630 source code
C++
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using i64 = long long;
using u64 = unsigned long long;
static constexpr int C_BITS = 23;
static constexpr int B_BITS = 12;
static constexpr int A_BITS = 12;
static constexpr i64 C_OFF = 4'000'000;
static inline u64 pack_line(int A, int B, i64 C) {
const i64 Co = C + C_OFF;
assert(0 <= A && A < (1 << A_BITS));
assert(-2048 <= B && B < 2048);
assert(0 <= Co && Co < (1LL << C_BITS));
const u64 Ao = (u64)A;
const u64 Bo = (u64)(B + 2048);
const u64 Co_u = (u64)Co;
return (Ao << (B_BITS + C_BITS)) | (Bo << C_BITS) | Co_u;
}
static std::vector<std::pair<int, int>> generate_points(int n) {
std::vector<std::pair<int, int>> pts;
pts.reserve(n);
i64 S = 290797;
for (int k = 0; k < n; ++k) {
S = (S * S) % 50515093;
const int x = (int)(S % 2000) - 1000;
S = (S * S) % 50515093;
const int y = (int)(S % 2000) - 1000;
pts.emplace_back(x, y);
}
return pts;
}
static std::pair<i64, i64> compute_MS(int n) {
const auto pts = generate_points(n);
std::vector<u64> keys;
keys.reserve((i64)n * (n - 1) / 2);
for (int i = 0; i < n; ++i) {
const auto [x1, y1] = pts[i];
for (int j = i + 1; j < n; ++j) {
const auto [x2, y2] = pts[j];
int dx = x2 - x1;
int dy = y2 - y1;
if (dx == 0 && dy == 0) continue;
const int g = std::gcd(std::abs(dx), std::abs(dy));
dx /= g;
dy /= g;
int A = dy;
int B = -dx;
i64 C = (i64)A * x1 + (i64)B * y1;
if (A < 0 || (A == 0 && B < 0)) {
A = -A;
B = -B;
C = -C;
}
keys.push_back(pack_line(A, B, C));
}
}
std::sort(keys.begin(), keys.end());
keys.erase(std::unique(keys.begin(), keys.end()), keys.end());
const i64 M = (i64)keys.size();
i64 parallel2 = 0;
for (i64 i = 0; i < M;) {
const u64 slope = keys[(size_t)i] >> C_BITS;
i64 j = i + 1;
while (j < M && (keys[(size_t)j] >> C_BITS) == slope) ++j;
const i64 m = j - i;
parallel2 += m * (m - 1);
i = j;
}
const i64 S = M * (M - 1) - parallel2;
return {M, S};
}
int main() {
{
const auto pts3 = generate_points(3);
assert((pts3[0] == std::make_pair(527, 144)));
assert((pts3[1] == std::make_pair(-488, 732)));
assert((pts3[2] == std::make_pair(-454, -947)));
}
{
const auto [m3, s3] = compute_MS(3);
assert(m3 == 3);
assert(s3 == 6);
}
{
const auto [m100, s100] = compute_MS(100);
assert(m100 == 4948);
assert(s100 == 24477690);
}
std::cout << compute_MS(2500).second << "\n";
return 0;
}
Python
import math
def solve():
n = 2500
S = 290797
pts = []
for _ in range(n):
S = S * S % 50515093
x = S % 2000 - 1000
S = S * S % 50515093
y = S % 2000 - 1000
pts.append((x, y))
lines = set()
for i in range(n):
x1, y1 = pts[i]
for j in range(i + 1, n):
x2, y2 = pts[j]
dx = x2 - x1
dy = y2 - y1
if dx == 0 and dy == 0: continue
g = math.gcd(abs(dx), abs(dy))
dx //= g; dy //= g
A = dy; B = -dx
C = A * x1 + B * y1
if A < 0 or (A == 0 and B < 0):
A, B, C = -A, -B, -C
lines.add((A, B, C))
lines_list = sorted(lines)
M = len(lines_list)
# Count parallel pairs (same slope = same (A, B))
from itertools import groupby
parallel2 = 0
for _, group in groupby(lines_list, key=lambda l: (l[0], l[1])):
m = sum(1 for _ in group)
parallel2 += m * (m - 1)
ans = M * (M - 1) - parallel2
return str(ans)
if __name__ == '__main__':
print(solve())
Java
import java.util.ArrayList;
import java.util.List;
public class Euler630 {
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
static long gcd(long a, long b) {
while (b != 0) {
long t = b;
b = a % b;
a = t;
}
return a;
}
static List<Point> generatePoints(int n) {
List<Point> pts = new ArrayList<>(n);
long S = 290797;
for (int k = 0; k < n; k++) {
S = (S * S) % 50515093;
int x = (int) (S % 2000) - 1000;
S = (S * S) % 50515093;
int y = (int) (S % 2000) - 1000;
pts.add(new Point(x, y));
}
return pts;
}
static long[] computeMS(int n) {
List<Point> pts = generatePoints(n);
long[] keysTmp = new long[n * (n - 1) / 2];
int idx = 0;
for (int i = 0; i < n; i++) {
Point p1 = pts.get(i);
for (int j = i + 1; j < n; j++) {
Point p2 = pts.get(j);
int dx = p2.x - p1.x;
int dy = p2.y - p1.y;
if (dx == 0 && dy == 0)
continue;
int g = (int) Math.abs(gcd(Math.abs(dx), Math.abs(dy)));
dx /= g;
dy /= g;
int A = dy;
int B = -dx;
long C = (long) A * p1.x + (long) B * p1.y;
if (A < 0 || (A == 0 && B < 0)) {
A = -A;
B = -B;
C = -C;
}
long Co = C + 4000000L;
long Ao = A;
long Bo = B + 2048;
long val = (Ao << 35) | (Bo << 23) | Co;
keysTmp[idx++] = val;
}
}
long[] keysStr = new long[idx];
System.arraycopy(keysTmp, 0, keysStr, 0, idx);
java.util.Arrays.sort(keysStr);
int uniqueCount = 0;
if (keysStr.length > 0) {
uniqueCount = 1;
for (int i = 1; i < keysStr.length; i++) {
if (keysStr[i] != keysStr[i - 1]) {
keysStr[uniqueCount++] = keysStr[i];
}
}
}
long M = uniqueCount;
long parallel2 = 0;
for (int i = 0; i < uniqueCount;) {
long slope = keysStr[i] >> 23;
int j = i + 1;
while (j < uniqueCount && (keysStr[j] >> 23) == slope)
j++;
long m = j - i;
parallel2 += m * (m - 1);
i = j;
}
long S = M * (M - 1) - parallel2;
return new long[] { M, S };
}
public static String solve() {
return Long.toString(computeMS(2500)[1]);
}
public static void main(String[] args) {
System.out.println(solve());
}
}