Hi
Modifying the Vijay Venkat Raghavan N's solution.
The idea is to store the data not in an array but hash with key the
slope.
Each entry in this hash has as value other hash where the key is the
pointId and value - list of the lines in which this point participates
with this slope. If while filling this structure you reach list with
size greather than 1 this list contains solution.
The complexity is O(n^2) to calculate all the slopes. O(1) to fill the
first Hash, O(1) to fill the second hash, O(1) to fill the list. There
is one other effort - printing the solution which depends on the number
of solutions which is something like logN. So finally you have
O(n^2)*O(1)*O(1)*O(1)*O(logN) = O(n^2logN).
class Line{
int point1;
int point2;
}
Hash<double slope, Hash<int point, List<Line> lines>>
Ridvan
