Submission #1867205

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

const int MX=100005,inf=0x3f3f3f3f;

typedef pair<int,int> pii;
#define fr first
#define se second
#define mp make_pair
#define pb push_back
typedef vector<int> vi;

int n,a,b;
map<int,set<pii> >x,y;
map<int,vi>xs,ys;
pii p[MX];
int vis[MX];
inline int dis(pii l,pii r){return max(abs(l.fr-r.fr),abs(l.se-r.se));}
inline void ins(int i){x[p[i].fr].insert(mp(p[i].se,i)),y[p[i].se].insert(mp(p[i].fr,i));}
inline void rem(int i){x[p[i].fr].erase(mp(p[i].se,i)),y[p[i].se].erase(mp(p[i].fr,i));}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		int u,v;cin>>u>>v;
		p[i].fr=u+v,p[i].se=u-v;
		//cout<<p[i].fr<<' '<<p[i].se<<endl;
	}
	for(int i=1;i<=n;i++)ins(i);
	deque<int>q;q.clear(),q.pb(a),q.pb(b);
	vis[a]=1,vis[b]=1,rem(a),rem(b);
	int D=dis(p[a],p[b]);
	while(!q.empty()){
		pii r=p[q.front()];q.pop_front();
		map<int,set<pii> >::iterator s=x.find(r.fr-D);
		if(s!=x.end()){
			for(set<pii>::iterator i=s->se.lower_bound(mp(r.se-D,~inf));i!=s->se.end()&&i->fr<=r.se+D;i=s->se.erase(i)){
				if(!vis[i->se])q.pb(i->se);
				vis[i->se]=1;
			}
		}
		s=x.find(r.fr+D);
		if(s!=x.end()){
			for(set<pii>::iterator i=s->se.lower_bound(mp(r.se-D,~inf));i!=s->se.end()&&i->fr<=r.se+D;i=s->se.erase(i)){
				if(!vis[i->se])q.pb(i->se);
				vis[i->se]=1;
			}
		}
		s=y.find(r.se-D);
		if(s!=y.end()){
			for(set<pii>::iterator i=s->se.lower_bound(mp(r.fr-D,~inf));i!=s->se.end()&&i->fr<=r.fr+D;i=s->se.erase(i)){
				if(!vis[i->se])q.pb(i->se);
				vis[i->se]=1;
			}
		}
		s=y.find(r.se+D);
		if(s!=y.end()){
			for(set<pii>::iterator i=s->se.lower_bound(mp(r.fr-D,~inf));i!=s->se.end()&&i->fr<=r.fr+D;i=s->se.erase(i)){
				if(!vis[i->se])q.pb(i->se);
				vis[i->se]=1;
			}
		}
	}
	//for(int i=1;i<=n;i++)cout<<vis[i]<<endl;
	long long c=0;
	for(int i=1;i<=n;i++)if(vis[i]){
		xs[p[i].fr].pb(p[i].se);
		ys[p[i].se].pb(p[i].fr);
	}
	for(map<int,vi>::iterator i=xs.begin();i!=xs.end();i++)sort(i->se.begin(),i->se.end());
	for(map<int,vi>::iterator i=ys.begin();i!=ys.end();i++)sort(i->se.begin(),i->se.end());
	for(int i=1;i<=n;i++){
		map<int,vi>::iterator s=xs.find(p[i].fr-D);
		c+=upper_bound(s->se.begin(),s->se.end(),p[i].se+D)-lower_bound(s->se.begin(),s->se.end(),p[i].se-D);
		s=xs.find(p[i].fr+D);
		c+=upper_bound(s->se.begin(),s->se.end(),p[i].se+D)-lower_bound(s->se.begin(),s->se.end(),p[i].se-D);
		s=ys.find(p[i].se-D);
		c+=lower_bound(s->se.begin(),s->se.end(),p[i].fr+D)-upper_bound(s->se.begin(),s->se.end(),p[i].fr-D);
		s=ys.find(p[i].se+D);
		c+=lower_bound(s->se.begin(),s->se.end(),p[i].fr+D)-upper_bound(s->se.begin(),s->se.end(),p[i].fr-D);
	}
	cout<<(c/2)<<endl;
	return 0;
}

Submission Info

Judge Result