曼哈顿距离转切比雪夫距离
同时这也是出题人偷的牛客的一道题
给定 $n$ 个点的坐标 $(x_i,y_i)$ 选择两个点满足其曼哈顿距离不小于 $d$ ，求方案数
不难画出，离一个点的曼哈顿距离相同的点构成一个菱形：
其满足对于 $(x_O,y_O),(x_i,y_i)$ 有 $\text{abs}(x_O-x_i)+\text{abs}(y_O,y_i)$
一个神奇的 $\text{trick}$ 是将其转化为切比雪夫距离，即，令 $x_i’=x_i+y_i\ ,\ y_i’=x_i-y_i$
不难得出此时的 $(x_O’,y_O’),(x_i’,y_i’)$ 的切比雪夫距离 $\max\left(|x_O’-x_i’|,|y_O’-y_i’|\right)$ 即是原图两点的曼哈顿距离
也就是离一点的曼哈顿距离相同的点构成的图形转化为矩形：
对于这个矩形，树状数组动态维护一下即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| const int N=201010;
int n,m,d,ans,l;
struct node{
int x,y;
friend bool operator <(const node &a,const node &b){ return a.y<b.y;}
}a[N];
int c[N<<1];
inline int lowbit(int x){ return x&-x;}
inline void add(int x,int y){ while(x<=l*4) c[x]+=y,x+=lowbit(x);}
inline int sum(int x,int res=0){ while(x>0) res+=c[x],x-=lowbit(x); return res;}
signed main(){
freopen("hole.in","r",stdin); freopen("hole.out","w",stdout);
scanf("%lld%lld%lld",&n,&d,&l);
for(rei i=1,x,y;i<=n;i++) scanf("%lld%lld",&x,&y), a[i].x=x+y,a[i].y=x-y, a[i].x+=2*l+1,a[i].y+=2*l+1;
sort(a+1,a+n+1);
for(rei i=1,j=1;i<=n;++i){
while(j<i && abs(a[i].y-a[j].y)>=d) add(a[j].x,-1),++j;
ans+=sum( min(l*4,a[i].x+d-1) )-sum(max(0ll,a[i].x-d));
add(a[i].x,1);
}
printf("%lld\n",(n*n-n)/2-ans);
getchar(),getchar();
return 0;
}
|
给定 $n$ 个点的坐标 $(x_i,y_i)$ 选择两个点满足其曼哈顿距离等于 $d$ ，求方案数
显然能转成切比雪夫距离，那么点对 $(x_1,y_1),(x_2,y_2)$ 需满足的条件即为：
或
通过对 $point$ 进行排序后二分查找，不难得到满足上述条件的 $y_l\sim y_r$ 或 $x_l\sim x_r$
考虑如何统计答案，对于合法的点对将两点连边
那么上述条件给定的一个合法区间，该区间内的点两两相连并向 $(x_a,y_a)$ 连边
维护一下每个点的出度，能与初始点 $a$ 连通的即为合法方案 (显然与 $b$ 连通的一定也与 $a$ 连通)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| const int N=1e5+100;
PII point[N],sorted_poi[N];
int fa[N],cnt[N],delta[N],id[N];
int x[N],y[N];
int n,a,b,dis;
ll ans;
inline int read(){ rei ans=0; char ch=getchar(); while(ch<'0' || ch>'9') ch=getchar(); while(ch>='0' && ch<='9'){ ans=(ans<<1)+(ans<<3)+(ch^48); ch=getchar();} return ans;}
inline bool cmp(int x,int y){ return point[x]<point[y];}
int get_fa(int x){ return fa[x]==x ? x : fa[x]=get_fa(fa[x]);}
inline void merge(int x,int y){ fa[ get_fa(x) ]=get_fa(y);}
inline void solve(int now){
for(rei i=1;i<=n;++i) id[i]=i;
sort(id+1,id+1+n,cmp);
memset(delta,0,sizeof delta);
for(rei i=1;i<=n;++i) sorted_poi[i]=point[ id[i] ];
for(rei i=1;i<=n;++i){
rei l=lower_bound(sorted_poi+1,sorted_poi+1+n,mk(sorted_poi[i].first+dis,sorted_poi[i].second-dis+now))-sorted_poi;
rei r=upper_bound(sorted_poi+1,sorted_poi+1+n,mk(sorted_poi[i].first+dis,sorted_poi[i].second+dis-now))-sorted_poi-1;
if(l<=r){
++delta[l],--delta[r];
merge(id[i],id[l]);
cnt[ id[i] ]+=r-l+1;
}
}
rei pre=0;
for(rei i=1;i<n;++i){
pre+=delta[i];
if(pre) merge(id[i],id[i+1]);
}
}
int main(){
n=read(),a=read(),b=read();
for(rei i=1;i<=n;++i) fa[i]=i;
for(rei i=1;i<=n;++i) x[i]=read(),y[i]=read(),point[i].first=x[i]+y[i],point[i].second=x[i]-y[i];
dis=abs(x[a]-x[b])+abs(y[a]-y[b]);
solve(0);
for(rei i=1;i<=n;++i) swap(point[i].first,point[i].second);
solve(1);
for(rei i=1;i<=n;++i) if(get_fa(i)==get_fa(a)) ans+=cnt[i];
printf("%lld\n",ans);
getchar(),getchar();
return 0;
}
|
切比雪夫距离转曼哈顿距离
给定平面上多个点坐标，求其余点到一点的切比雪夫距离之和的最小值
注意，如下定义即为切比雪夫距离： 点 $(x,y)$ 和周围 $8$ 个点 $(x\pm1,0\ ;\ y\pm 1,0 )$ 的距离为 $1$
显然如此转化后点 $(x,y)$ 变为 $\left(\frac{x+y}{2},\frac{x-y}{2}\right)$
枚举中心点 $i$ ，分别讨论横纵坐标对答案的贡献，以横坐标为例
若点 $j$ 横坐标 $x_j$ 满足 $x_j\leq x_i$ ，则其贡献为 $x_i-x_j$ ，否则为 $x_j-x_i$
排序后，若前 $k$ 个的横坐标 $\leq x_i$ ，那么所有横坐标对答案有贡献：
考虑用前缀和维护 $2，3$ 项：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const int N=1e5+100;
int n,x[N],y[N],xx[N],yy[N],prex[N],prey[N];
ll ans=1e17;
signed main(){
scanf("%lld",&n);
for(rei i=1,u,v;i<=n;++i) scanf("%lld%lld",&u,&v),x[i]=xx[i]=u+v,y[i]=yy[i]=u-v;
sort(xx+1,xx+1+n); sort(yy+1,yy+1+n);
for(rei i=1,x,y;i<=n;++i) prex[i]=prex[i-1]+xx[i],prey[i]=prey[i-1]+yy[i];
for(rei i=1,k1,k2;i<=n;++i){
k1=lower_bound(xx+1,xx+n+1,x[i])-xx;
k2=lower_bound(yy+1,yy+n+1,y[i])-yy;
ll ansx=(ll) k1*x[i]-2ll*prex[k1]+prex[n]-(ll) (n-k1)*x[i];
ll ansy=(ll) k2*y[i]-2ll*prey[k2]+prey[n]-(ll) (n-k2)*y[i];
ans=min(ans,ansx+ansy);
}
printf("%lld\n",ans/2);
getchar(),getchar();
return 0;
}
|