filo's blog

Closest pair of points

By filo, 10 years ago, In English

So this problem is about finding the closest pair of points on the plane,here's my code which gets TLE. I think my code should work in logarithmic time,but it doesn't seem so.So I kindly ask to provide any advices or improvements,for those people who will try to help me,for simplicity,comments are inserted in the code.

Thanks.

UPDATE: Got accepted thanks to Alex_2oo8's observations,no more help needed

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

Comments Comments (6)
| Write comment?
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hi, the problem seems to be in the part under comment //Choosing elements from Secondary[] array. You iterate over all n points, so the complexity of every call to SolveClosest is O(n) and in total you receive O(n2) complexity.

The main idea is that SolveClosest(l, r) must work in poly(r - l) time (if we don't consider the recursive calls). The only problem is that we want to have a subarray Main[l..r] in sorted by y order. So here are two solutions:

  1. Each time sort the subarray Main[l..r]. This results in O(len log len) complexity for call to SolveClosest(l, r), where len = r - l + 1. And O(n log2 n) in total.
  2. Use mergesort during the SolveClosest process. This results in O(len) complexity for call and O(n log n) in total.
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks,it was really helpful,I'll try to implement those improvements asap

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

      By the way, just found that your template contains rather bad defines:

      #define Min(a,b) (a<b?a:b)
#define Max(a,b) (a>b?a:b)

      For example, in your solution the next line, replacing SolveClosest with just f

      ll d = Min(f(l, Mid), f(Mid + 1, r));

      converts to

      ll d = (f(l, Mid) < f(Mid + 1, r) ? f(l, Mid) : f(Mid + 1, r));

      and... performs 3 recursive calls! I don't thing you really want this to happen.

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

        lol haven't mentioned it thanks :D

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

I got AC in this problem:

http://codeforces.com/problemset/problem/429/D

My submission is here:

http://codeforces.com/contest/429/submission/6603978

My algorithm is the same with Wikipedia's one.

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

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

    Have tried checking other participants solutions,as well as read an article on Wiki before posting this but didn't find it helpful :/ Anyway thanks for your time Alex_2oo8's advises are enough till now I think :)

    → Reply