2
Help with 2D Grid Rotation
source link: https://codeforces.com/blog/entry/111196
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Hi all!
I had a question about a commonly known trick for this problem: — Given a set of points(x and y are between 0 and 1e5), calculate the total number of pairs of points that are within a Manhattan distance of 'k'.
I know that you can use a BIT with a sweepline by changing each point to (x + y, x — y). My question is: How does 'k' change when I do the grid rotation / how do I perform queries after the grid rotation?
Thank you in advance!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK