Azret's blog

Closest point
By Azret, history, 9 years ago, translation, In English

Hi all!

Straightly to the problem — you are given a set of N (1 < N <  = 105) distinct points with integer coordinates on coordinate plane. For each point you need to find number of closest point to it (from set, expect itself). If there are more than one output point with minimum number.  - 104 <  = xi, yi <  = 104

UPD Distance between points (x1, y1) and (x2, y2) is equal to |x1 - x2| + |y1 - y2|. :P

Input
4
0 0
1 1
1 0
0 1

Output
3 3 1 1
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
9 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Similar problem: Given N points (1<=N<=100000) Draw a straight line that connects maximum number of those points and output the count of those points that are in the straight line.

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

Similar problem:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=324&page=show_problem&problem=2392

→ Reply
»
9 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Rotate the plane by 45 degrees.

Now distance between two points is max(|x1 - x2|, |y1 - y2|).

Points at the same distance represents a square with edges parallel to the axis.

You can use binary search to answer for each point. While checking whether there is a point in the square or not, one can use 2D data structure. Choose a data structure that you are familiar with. I would implement a range tree(with fractional cascading) or a persistent segment tree.

Overall complexity is O(N(logN)2)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I can't understand how the 45 degree rotation works, can anyone explain please?

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

    Your algorithm works in O(N (log n) ^ 2 * log (answer)).

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

      Actually, it is O(NlogNlog(answer)) so O(N(logN)2) is not that bad upper bound too.

      You probably missed "fractional cascading" part.

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

It can be easily solved with 2d segment tree + binary search for answer. For each point lets make binary search for answer. We have to check is there some another point that distance between them is less than answer. How to check it? Lets rotate all points at 45 degree. And for checking current value of binary search we have to calculate some sum at rectangle (Easily with 2d-segment tree).

But, I also think that this problem can be solved with standart divide and conquer method. Just solve it as for Euclidian geometry with another function that calculates distance between two points with abs formula.

First method works in O(n log^3 n). This solution is 100% right :). It is pretty easy to prove that binary search works here.

Second method works in O(n log n), but I have no idea how to prove. It will be fantastic if someone give me prove of it or extra test case.

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you all! Accepted! Sleepless night cost it. :)

For who are interested here is solution.

→ Reply