WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
This is a pretty straightforward question, as the number of solvers suggests. Given a set of points in the plane, we take a look at the set of all lines that can be formed by joining pairs of points in . We need to calculate and the number of times any two of these lines intersect.
We can characterize both equality of lines and two lines intersecting using the slope. Two lines can be declared equal if and only if they have the same slope and share a point. Two distinct lines are going to intersect if and only if they have distinct slopes.
Thus it will make sense to organize all the lines by their slope as the first step. Since all of the points in this problem are going to be integral, we may associate each line with its normalized slope – which has integral coprime coordinates, and the first non-zero coordinate is positive. Notice that we will be using only integers and thus we need not worry about any possible floating point inaccuracies. Throughout, we will also take care not to include any line that shares a point with any other line with the same slope. Letting denote the number of lines with slope , we simply have:
There will be at most distinct slopes, so the above quantities can be calculated in time, given . To compute ’s, we will iterate over all pairs of points, computing the normalized slope vector for each pair (this will involve calling the greatest common divisor). The overall complexity is thus with being the size of the largest coordinate present in .
The following piece of Julia code gives the answer in about 50 seconds.