AT2160 へんなコンパス / Manhattan Compass

传送门

乍一看像是一个计算几何，然后想到了BFS，但是苦于无奈\(O(n^2)\)不会优化

然后以下参考zjq_shadow大佬的思路

显然发现曼哈顿距离很麻烦，除了暴力枚举貌似没什么很好的办法

考虑将坐标轴旋转\(45^\circ\)，然后就可以将曼哈顿距离转化为切比雪夫距离，坐标为\((x,y)\)的点坐标就变为\((x+y,x-y)\)

那么对于\(x1,y1\)要求的\(x2,y2\)，需满足

\[|x1-x2|=dis\\
|y1-y2|<=dis
\]

或者

\[|y1-y2|=dis\\
|x1-x2|<=dis
\]

然后就可以排序，排序之后每个点对应的就是一段区间了

但是这样并不好统计答案，所以考虑转化一下问题

我们可以把满足条件的点对都连边，这样的话答案就是\(a\)和\(b\)所在的联通块的点的度数和

然后暴力连边复杂度依然爆炸

考虑到相邻的点对应的区间差别不大，去连重复的区间里的点显然没意义，所以记下一个上次连的最后一个点\(pos\)，每次从\(pos\)开始连边就好了

有一个小细节：观察上面的两种情况，对于第一种情况，如果算了\(|y1-y2|=dis\)，在第二种情况中再算\(|x1-x2|=dis\)是会重复计算的，所以要处理一下

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

void read(int &x){

    char ch;bool ok;

    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;

    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;

}

#define rg register

const int maxn=1e5+10;bool vis[maxn];

int n,a,b,len,sum[maxn],pre[maxn*10],nxt[maxn*10],h[maxn],cnt;

long long ans;

struct oo{int x,y,id;}s[maxn];

void add(int x,int y){

    pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;

    pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt;

}

bool cmp(oo a,oo b){return a.x==b.x?(a.y<b.y):a.x<b.x;}

void solve(int dis){

    sort(s+1,s+n+1,cmp);

    int l=1,r=0,pos=1;

    for(rg int i=1;i<=n;i++){

        while(l<n&&(s[l].x<s[i].x-len||(s[l].x==s[i].x-len&&s[l].y<s[i].y-dis)))l++;

        while(r<n&&(s[r+1].x<s[i].x-len||(s[r+1].x==s[i].x-len&&s[r+1].y<=s[i].y+dis)))r++;

        sum[s[i].id]+=r-l+1;pos=max(pos,l);

        while(pos<=r)add(s[i].id,s[pos].id),pos++;

        pos--;

    }

}

void dfs(int x){

    vis[x]=1;ans+=sum[x];

    for(rg int i=h[x];i;i=nxt[i])

        if(!vis[pre[i]])dfs(pre[i]);

}

int main(){

    read(n),read(a),read(b);

    for(rg int i=1,x,y;i<=n;i++){

        read(x),read(y),s[i].id=i;

        s[i].x=x+y,s[i].y=x-y;

    }

    len=max(abs(s[a].x-s[b].x),abs(s[a].y-s[b].y));

    solve(len);

    for(rg int i=1;i<=n;i++)swap(s[i].x,s[i].y);

    solve(len-1),dfs(a);

    printf("%lld\n",ans);

}

巴特西

AT2160 へんなコンパス / Manhattan Compass

传送门

最新文章

热门文章