aajjbb's blog

Distance between a set of points in Linear time
By aajjbb, 12 years ago, In English

Hi, I'm stuck in such a problem who ask's for the given set G of points in a plane, for each point i, how many points s are less than an integer D close to point i.

My fist and naive approach was an O(N^2) solution looking for the distance from all points to points, which didn't got TLE.

What is the better approach ?

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, give link to problem.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use convex hull which garanted O(NlogN) time

→ Reply