oneandonly's blog

By oneandonly, history, 14 months ago, In English,

Given a grid with R (Rows) and C (Coloumns) and N points (R,C) within the grid. I need to find the count of maximum mutually equidistant collinear points.

Mutually equidistant points here means, Every point on that line should be at equal distance with its neighbouring point on that line only (1,1 -> 3,3 -> 5,5 -> 7,7).

A line would be discarded if it contains non-mutually equidistant points(or point). (1-1 -> 3,3 ->5,5 -> 6,6-> 7,7 is an invalid line).

I came up with N^3 complexity approach, i.e consider any two points and check for every other point for collinearity and after each iteration , checking whether all the collinear points are mutually equi-distant or not. It's too slow to work. Is there any better approach?

Thank you.


14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, Can you share your code or algorithm to at least to think in that direction? It might help for all to improve it.