You are not logged in. Please login at www.codechef.com to post your questions!

×

Maximum mutually equidistant collinear points.

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 is an invalid line).

I came up with N^3 complexity approach, but it's too slow to work. Is there any better approach?

Thank you.

asked 21 Apr, 09:32

wolfroger's gravatar image

2★wolfroger
486
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×843
×364
×24
×1

question asked: 21 Apr, 09:32

question was seen: 161 times

last updated: 21 Apr, 09:32