mjguru's blog

Need help on a manhattan distance problem
By mjguru, history, 8 years ago, In English

You are given a grid square of size R x H (R & H <= 10^9). You are also given N special points (N <= 5000). Each of the N special points has a different power Ri (R <= 10^9) associated with it. Each of these points can influence all points of the grid within a manhattan distance of R (if the manhattan distance between the special point and any other point is <= Ri, it will be influenced). Find out how many points are totally influenced in the grid.

I thought about some sort of coordinate compression + Line Sweep algorithm + dp but could not get it through. I also tried converting points into x + y & x — y + coordinate compression + BIT but could not get any ideas. Please help. I am so stuck! Thanks in advance.

Edit: I meant lattice points while referring to points in all cases.

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

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

Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).

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

Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

First convert coordinates to x + y and x — y when you need to find area of union of squares. it is a standart task, you can find solution description at topcoder: Line sweep tutorial

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

    Could you elaborate. What would be the edge size? Where will be the corners?

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

      ok. at first you have coordinates x, y |x-a|+|y-b|<=t

      when if you solve this, you will have a square rotated by 45 degrees. and 4 corners

      <x, y-t>

      <x, y+t>

      <x-t, y>

      <x+t, y>

      ok, lets rotate it by 45 degress.

      <x+y-t, x-y+t>

      <x+y+t, x-y-t>

      <x+y-t, x-y-t>

      <x+t+y, x-y+t>

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I do not think that is correct. Consider just one special point at 10, 10 of power 1. It will influence the following points: (10, 10), (10, 9), (10, 11), (9, 10), (11, 10). However, by your method, it will be converted into a rectangle of width 2 whose area will be four. Please correct me if I am wrong or have misunderstood you

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

          you need another function of area inside line sweep

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

            Could you explain with an example? I am having a really hard time understanding your approach.

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

Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).

→ Reply