N points, dist btw two points is defined as min(abs(x1-x2), abs(y1-y2)).find kth min dist.

Revision en1, by 7KIRA1999, 2023-05-07 09:20:13

I am trying to solve the given problem from here :

https://stackoverflow.com/questions/69444907/given-an-array-of-n-points-the-distance-between-two-points-is-defined-as-minab

using very similar problem : https://www.spoj.com/problems/NKPAIRS/en/

The code for this spoj problem looks something like this -

int n, m=50000, x[100005], y[100005];
long long ans;
struct segtree {
int v[2*L];
void upd (int P, int V) {
P += L;
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int S, int E) {
S += L;
E += L;
int R = 0;
while(S <= E) {
if(S % 2 == 1) R += v[S++];
if(E % 2 == 0) R += v[E--];
S /= 2;
E /= 2;
}
return R;
}
} seg;

vector<int> b[150005];

long long solve2 (int d) {
for(int i=1;i<=n;i++) {
b[x[i]+y[i]-1].push_back(x[i]-y[i]+m);
}
for(int i=1;i<=2*m;i++) {
for(auto &T : b[i]) {
ans += seg.get(max(0,T-d), min(2*m,T+d));
seg.upd(T, 1);
}
if(i - d <= 0) continue;
for(auto &T : b[i-d]) {
seg.upd(T, -1);
}
}
return ans;
}


What changes should be done in this part so that the distance factor is updated in regards to my problem ?

Any help is appreciated.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 7KIRA1999 2023-05-07 09:20:13 1502 Initial revision (published)