Gym-102569C Manhattan Distance 曼哈顿距离的转换 二分
题意
给定平面上的\(n\)个整点\((x_i,y_i)\),整点之间会两两产生曼哈顿距离,求第\(k\)小的曼哈顿距离大小。
\[2 \leq n \leq 1e5\\ 1 \leq k \le \frac{n(n+1)}{2}\\ -10^8 \leq x_i,y_i \le 10^8 \]分析
此题如果直接做会发现没什么想法
因此利用曼哈顿距离的性质:
对于点\((x_i,y_i)\),\((x_j,y_j)\)。曼哈顿距离\(d = |x_i - x_j| + |y_i - y_j|\),切比雪夫距离\(d' = max(|x_i - x_j|,|y_i - y_j|)\)
变换:\((x_i,y_i) => (x_i +y_i,x_i - y_i),(x_j,y_j) => (x_j +y_j,x_j - y_j)\)
那么求这两点的曼哈顿距离就等价为了求切比雪夫距离
回到这题,我们把所有点变成求切比雪夫距离。
题目变为求第\(k\)小的切比雪夫距离,这显然是可以二分答案的。问题又变为求所有点中,距离\(d \leq 给定dis\) 的对数。
显然,可以固定\(i\),枚举\(j < i\)中符合条件的对数。根据切比雪夫距离的性质,要同时满足\(|x_i - x_j|和|y_i - y_j|\)小于等于dis,那么我们对x排序,对y建立权值树状数组表示符合条件的点,每次查询\([y-dis,y+dis]\)范围的个数,为了保证\(x\),可以对x排序,用双指针移动来保证。
代码
struct BIT{
vector<int> c;
int n;
BIT(int n):n(n),c(n + 1,0) {}
void add(int pos,int x){
for(;pos <= n;pos += pos & -pos)
c[pos] += x;
}
int ask(int x){
int res = 0;
for(;x >= 1;x -= x & -x){
res += c[x];
}
return res;
}
};
vector<int> h;
ll k;
int n;
int ans;
int get(int x){
return lower_bound(h.begin(),h.end(),x) - h.begin() + 1;
}
int check(int dis,vector<pii>& p){
BIT bit(n);
ll cnt = 0;
for(int i = 1,j = 1;i <= n;i++){
while(j < i && p[j].fi < p[i].fi - dis) {
bit.add(get(p[j].se),-1);
j++;
}
int up = upper_bound(h.begin(),h.end(),p[i].se + dis) - h.begin() ;
int down = lower_bound(h.begin(),h.end(),p[i].se - dis) - h.begin() + 1;
cnt += bit.ask(up) - bit.ask(down - 1);
bit.add(get(p[i].se),1);
}
return cnt;
}
signed main(){
n = rd();
k = rd();
vector<pii> v(n + 1);
for(int i = 1;i <= n;i++){
int x = rd();
int y = rd();
v[i] = make_pair(x + y,x - y);
h.push_back(x - y);
}
sort(h.begin(),h.end());
h.erase(unique(h.begin(),h.end()),h.end());
sort(v.begin() + 1,v.end());
int l = 1,r = 5e8 + 10;
while(l <= r) {
int mid = l + r >> 1;
if(check(mid,v) >= k) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans;
}