Description
Solution
问题其实就是从一个点出发，每次可以走与其曼哈顿距离恰好为一个常数\(d\)的点
显然不可能一一走完所有的边，这样复杂度下界至少是\(O(ans)\)
我们采用折中方式：间接统计
（1）找出从起始点能到达哪一些点
（2）统计对于这些点之中的每一个点，与其距离为d的点有多少，求和除二就是总边数
首先考虑第一步，如果我们通过枚举边的思路进行广搜，又要触及边的数目过多这一限制。考虑距离一个点\((x_0,y_0)\)曼哈顿距离为\(d\)的点\((x,y)\)应该满足什么特征，分四类：左上左下右上右下。左上右下的限制都是形如\(x-y=x_0\pm y_0\pm d\)且\(x\)在一定范围内的点，右上坐下的限制都是形如\(x+y=x_0\pm y_0\pm d\)的点
枚举四种情况时，两个符号可以直接定下来，关键是对于每个\(a\)，组织起满足\(x+y=a\)或\(x-y=a\)的点，并按\(x\)大小维护。由于我们不需要统计\(x\)在某个范围内的数具体有多少个，而仅仅是需要迭代枚举功能，我们马上想到内层应该要用一个set维护这一些点。那么外层是一个\(x+y\)或\(x-y\)的索引，关于索引，用map
所以用两个map套set，维护\(x+y\)和\(x-y\)的点的信息。对于一个点，它在两个map中都有且仅有一个存在
那么广搜时只需在map上查询所需的特征对应的set，并确定\(x\)值范围，在set上迭代枚举即可
如果这样，我们发现这个复杂度下界至少是边数。我们第一步是找出所有联通点，而不是统计边数，每个点显然入一次队即可。所以如果一个点入队，我们就把它在两个map中的存在删除。这样就能保证复杂度与点数相关
接下来是第二步，由于是无序边，我们想到顺序往右扫、并单向往左统计连边
对于关键点按\(x\)排序，顺序右扫。考虑先前加入的点与当前点能连多少边。那么我们还是需要用\(x+y\)和\(x-y\)作为两个特征储存先前的点。与（1）不一样的是，这回我们要统计等于某个特征值、\(x\)在某个范围内的点有多少个。这回我们不用set，而用map套vector，这样就可以通过二分来确定某个范围内有多少个点。由于\(x\)递增、我们要查询的范围也和\(x\)有关，所以当前点加入信息时，直接将其pushback到每个vector后即可
Code
#include <cstdio>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=100005;
int n,sa,sb;
int stdDis;
struct Point{
int x,y,id;
void read(int _id){
scanf("%d%d",&x,&y);
id=_id;
}
};
Point p[N],a[N];
struct CompairByX{
bool operator() (const int &a,const int &b){
return p[a].x<p[b].x;
}
}tcmp;
map<int,set<int,CompairByX>> keyp,keyd; // x+y/x-y
int acnt;
inline int abs(int x){
return x>=0?x:-x;
}
int calc(Point &a,Point &b){
return abs(a.x-b.x)+abs(a.y-b.y);
}
void readData(){
scanf("%d%d%d",&n,&sa,&sb);
for(int i=1;i<=n;i++)
p[i].read(i);
stdDis=calc(p[sa],p[sb]);
}
void addPoint(Point &a){
keyp[a.x+a.y].insert(a.id);
keyd[a.x-a.y].insert(a.id);
}
void remPoint(Point &a){
keyp[a.x+a.y].erase(a.id);
keyd[a.x-a.y].erase(a.id);
}
void findConnectedSet(){
// store into a[acnt]
acnt=0;
for(int i=1;i<=n;i++)
addPoint(p[i]);
static queue<int> q;
static bool vis[N];
q.push(sa);
vis[sa]=true;
remPoint(p[sa]);
while(!q.empty()){/*{{{*/
int u=q.front(),v,cur;
q.pop();
a[++acnt]=p[u];
cur=p[u].x+p[u].y+stdDis;
for(auto i=keyp[cur].lower_bound(u),j=i;i!=keyp[cur].end()&&p[*i].x<=p[u].x+stdDis;i=j){ //right
j++;
v=(*i);
if(!vis[v]){
vis[v]=true;
q.push(v);
remPoint(p[v]);
}
}
cur=p[u].x+p[u].y-stdDis;
p[n+1]=(Point){p[u].x-stdDis,0};
for(auto i=keyp[cur].lower_bound(n+1),j=i;i!=keyp[cur].end()&&p[*i].x<p[u].x;i=j){ // left
j++;
v=(*i);
if(!vis[v]){
vis[v]=true;
q.push(v);
remPoint(p[v]);
}
}
cur=p[u].x-p[u].y+stdDis;
for(auto i=keyd[cur].lower_bound(u),j=i;i!=keyd[cur].end()&&p[*i].x<=p[u].x+stdDis;i=j){ //right
j++;
v=(*i);
if(!vis[v]){
vis[v]=true;
q.push(v);
remPoint(p[v]);
}
}
cur=p[u].x-p[u].y-stdDis;
for(auto i=keyd[cur].lower_bound(n+1),j=i;i!=keyd[cur].end()&&p[*i].x<p[u].x;i=j){ // left
j++;
v=(*i);
if(!vis[v]){
vis[v]=true;
q.push(v);
remPoint(p[v]);
}
}
}/*}}}*/
}
bool cmpByX(const Point &a,const Point &b){
return a.x<b.x;
}
map<int,vector<int>> xp,xd;
void calcAnswer(){
ll ans=0;
sort(a+1,a+1+acnt,cmpByX);
for(int i=1;i<=acnt;i++){
int cur=a[i].x-a[i].y-stdDis,left;
left=lower_bound(xd[cur].begin(),xd[cur].end(),a[i].x-stdDis)-xd[cur].begin();
ans+=xd[cur].size()-left;
cur=a[i].x+a[i].y-stdDis;
left=lower_bound(xp[cur].begin(),xp[cur].end(),a[i].x-stdDis)-xp[cur].begin();
if(left<xp[cur].size()&&xp[cur][left]==a[i].x-stdDis)
left++;
ans+=xp[cur].size()-left;
xd[a[i].x-a[i].y].pb(a[i].x);
xp[a[i].x+a[i].y].pb(a[i].x);
}
printf("%lld\n",ans);
}
int main(){
readData();
findConnectedSet();
calcAnswer();
return 0;
}