oneandonly's blog

By oneandonly, history, 7 years 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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?