Блог пользователя filo

Closest pair of points

Автор filo, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.
→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      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.

      → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got AC in this problem:

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

My submission is here:

http://mirror.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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)

    → Ответить