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.
Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).
Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).
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
Could you elaborate. What would be the edge size? Where will be the corners?
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>
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
you need another function of area inside line sweep
Could you explain with an example? I am having a really hard time understanding your approach.
Auto comment: topic has been updated by mjguru (previous revision, new revision, compare).