【模拟】AtCoder2160 Manhattan Compass

分析:

模拟实现题。。。把坐标轴转一下然后暴力求就行了。
转了一下坐标轴，问题就变成以p为中心，与新的坐标轴平行的，边长为2*d的正方形上的点能够与p相连。

方便起见，把答案分成两部分求

然后可以分别考虑这两部分，分别扫描这两部分即可。
只不过有个技巧，如果使用并查集储存能到达哪些点，那么每次连的边应该从与上个点最后一个连的点开始即可。（没必要重复连边，因为那部分已经连上同一个点，所以只需要连一条就能把所有点连在一起）。这样一来，连边的次数均摊下来就是2*N次了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
typedef long long ll;
int n,st;
ll d;
int fa[MAXN];
ll siz[MAXN];
ll cnt[MAXN];
int get_fa(int x){
    if(fa[x]==0)
        return x;
    fa[x]=get_fa(fa[x]);
    return fa[x];   
}
vector<pair<ll,int> >mp;
struct node{
    ll x,y;
    int id;
    bool operator < (const node &a) const {
        if(x!=a.x)
            return x<a.x;
        return y<a.y;
    }
}p[MAXN];
ll dist(int x,int y){
    return abs(p[x].x-p[y].x)+abs(p[x].y-p[y].y);
}
void merge(int x,int y){
    //PF("{%d %d}\n",x,y);
    x=get_fa(x);
    y=get_fa(y);
    if(x!=y)
        fa[x]=y;
}
void solve(ll now){
    mp.clear();
    int las=1;
    vector<pair<ll,int> >::iterator  lasx;
    bool flag=0;
    for(int i=1;i<=n;i++){
        if(p[i].x!=p[i-1].x){
            mp.clear();
            flag=1;
        }
        while(p[i].x-p[las].x>d&&las<=n)
            las++;
        while(p[i].x-p[las].x==d&&las<=n){
            mp.push_back(make_pair(p[las].y,p[las].id));
            las++;
        }
        vector<pair<ll,int> >::iterator it=lower_bound(mp.begin(),mp.end(),make_pair(p[i].y-d+now,0));
        if(flag){
            flag=0;
            lasx=mp.begin();
        }
        lasx=max(lasx,it);
        if(it==mp.end()||it->first >p[i].y+d-now)
            continue;
        for(;lasx!=mp.end()&&lasx->first <= p[i].y+d-now;lasx++){
            int x=lasx->second;
            int y=p[i].id;
            if(x>y)
                swap(x,y);
            merge(x,y);
        }
        cnt[p[i].id]+=(lasx-it);
        //PF("[%d %d %d]\n",p[i].id,cnt[p[i].id],lasx-it);
        if(lasx!=it)
            lasx--;
    }
}
int a,b;
int main(){
    SF("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++){
        SF("%d%d",&p[i].x,&p[i].y);
        p[i].id=i;
    }
    d=dist(a,b);
    for(int i=1;i<=n;i++){
        ll x=p[i].x;
        ll y=p[i].y;
        p[i].x=x-y;
        p[i].y=x+y;
    }
    sort(p+1,p+1+n);
    solve(0);
    for(int i=1;i<=n;i++)
        swap(p[i].x,p[i].y);
    sort(p+1,p+1+n);
    //PF("----------\n");
    solve(1);
    for(int i=1;i<=n;i++)
        siz[get_fa(i)]+=cnt[i];
    PF("%lld",siz[get_fa(a)]);
}